题目：31. 下一个排列

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

思路

下一个排序:
[1,2,3] 这个组合成的整数是123; 用这三个整数进行组合是下一个整数是132;需要在原来的列表进行交换；

1. 从后向前查找到倒序的第一个位置，转折点在先升序再倒序这里，记录下数组的小标；
2. 继续从后向前遍历，找到第一个比步骤1找出的数大的数，交换俩个数的位置；
3. 从步骤1找出的下一个位置开始进行升序遍历；

代码

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        # 题目的意思是找到排序的下一个
        # 将列表的元素进行组合拼成一个整数
        # 如果是降序变为升序，
        left = -1
        right = 0
        # 找第一个相邻升序对
        for i in range(len(nums)-1,-1,-1):
            if nums[i-1]<nums[i]:
                left = i-1
                break
        if left == -1: # 说明没找到
            nums.sort()
            return
        for j in range(len(nums)-1, left, -1):
            if nums[j]>nums[left]:
                right = j
                break
        nums[left], nums[right] = nums[right], nums[left]

        x = left+1
        y = len(nums)-1

        while x<y:
            nums[x], nums[y] = nums[y], nums[x]
            x += 1
            y -= 1

        return