每日一题20201118（31. 下一个排列）

再看有下一个排序的情况，我们需要先从右侧找到一个比最右边数字小的数.
然后再和右边第一个大于这个数的数进行交换，以571632为例子：
第一个小于右侧数字的数是1，第一个大于1的数字是2，交换之后:
572631, 由于之前确定的，是通过升序找到的1，所以还需要反转2后面的数字: 572136 就是最终结果了！
正好可以和上面反转的一起处理。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 左侧的第一个非升序数字，这里也可以len(nums)-2
        j = len(nums)-1
        while j-1 >= 0:
            if nums[j] > nums[j-1]:
                break
            j -= 1
        # 如果j-1>=0说明找到了这个数字，否则说明数组
        # 是降序排列的
        if j-1 >= 0:
            right = len(nums)-1
            # 找到右边第一个大于nums[j-1]的数字
            while right > j-1 and nums[right] <= nums[j-1]:
                right -= 1
            # 交换他们
            nums[j-1], nums[right] = nums[right], nums[j-1]
            self.reverse(nums, j, len(nums)-1)
        else:
            self.reverse(nums, 0, len(nums)-1)
    # 反转数组
    def reverse(self, nums, i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
        return nums