题解 | #下一个排列#

整数数组的一个排列 就是将其所有成员以序列或线性顺序排列。 给你一个整数数组 nums ，找出 nums 的下一个排列。必须原地修改，只允许使用额外常数空间。 下一个排列 按照字典序的下一个更大的排列；若已经是最大值，下一个排列为最小序号

问题分析：元素按升序排列的下一个元素

举例：输入[1,2,3,8,5,7,6,4] 输出：[1,2,3,8,6*,4,5,7]

1. 解题工具：

• 双指针
• 数组遍历
• 查找下一个元素算法

2. 下一个元素查找逻辑

• step1 在尽可能靠右的低位进行交换，找到最靠右的，升序片段

  1）从后往前遍历，确定需要调整的整数的位置i 2）找到满足nums[i] < [i + 1]的相邻一对元素(i, i + 1)

• step 2 如果i<0:说明当前元素是最大值，则需要将序列倒置。执行步骤4

• step3 从i的后序片段中，选择最小大于nums[i]的数值，将其与nums[i]对调

#由于[i,end]为降序排列，k从后往前遍历，找到的第一个值即符合条件
while i>=0 and nums[k] > nums[i]:
	找到k
    swap(nums[i],nums[k])

• step4: 将序列片段倒置

start = i + 1
end = len(nums)
swap(nums[start], nums[end])