前往此题

解题思路

此题的大致意思是组合出下一个更大的整数，比如[1,2,3,4,5,6]把它看成一个整数123456，需要组合出[1,2,3,4,6,5]，即123465

以求15847531为例：

1. 先从后往前找到相邻的升序元素（i, j）, 即i = 3, j = 4, 对应的值为4, 7
2. 然后在(j, end)中从后往前找到第一个大于A[i]的值A[k]，这里A[i]为4, 即A[k]为5
3. 将A[i]与A[k]互换，此时(j, end)必定为降序，然后倒置它们换成升序即可

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            k = len(nums) - 1
            while k >= 0 and nums[k] <= nums[i]:
                k -= 1
            nums[i], nums[k] = nums[k], nums[i]
        
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1