LeetCode-31-下一个排列

原题链接：https://leetcode-cn.com/problems/next-permutation/

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。

解题思路：

1. 从后向前遍历寻找较小数，当a[i]<a[i+1], 此时i为较小数的index；
2. 从后向前遍历至i+1，寻找比较小数a[i]大一点的的index，为较大数j的位置；
3. swap i和j位置上的值；
4. 对i之后列表进行升序。

Python3代码：

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        start = -1
        for i in range(len(nums)-2, -1, -1):
            if nums[i] < nums[i+1]:
                start = i
                break

        end = 0
        if start >=0:
            for j in range(len(nums)-1, start, -1):
                if nums[j] > nums[start]:
                    end = j
                    nums[start], nums[end] = nums[end], nums[start]
                    break
        
        
        left, right = start+1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1