下一个排列算法

31. 下一个排列 - 力扣（LeetCode）

找出这个数组排序出的所有数中，刚好比当前数大的那个数

比如当前 nums = [1,2,3]。这个数是123，找出1，2，3这3个数字排序可能的所有数，排序后，比123大的那个数 也就是132

如果当前 nums = [3,2,1]。这就是1，2，3所有排序中最大的那个数，那么就返回1，2，3排序后所有数中最小的那个，也就是1，2，3 -> [1,2,3]

思路

1、 我们希望下一个数组组成的数比现在的数大，因此只需要从后向前，将后面稍大的数和前面稍小的数交换。例 1234587，因此只需要将5，7进行交换 得出更大的数 1234785

从后向前，查找到第一个i，满足数组a[i] < a[i+1]

再从[i+1,n)中从后向前找到 第一个元素 j 满足 a[i] < a[j] ,这样较大数 为a[j]

2、还希望下一个数在其他比原数组成的数中最小。

交换 a[i],a[j],此时可以发现[i+1,n) 必为降序， 因此可以用双指针反转区间，使里面数值便为升序.

这时 该数组为稍大的数

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1
            while j >= 0 and nums[i] >= nums[j]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

借鉴：31. 下一个排列 - 力扣（LeetCode）