下一个排列

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        # 思考：
        # 1. 对于某个位置i，如果前面保持相同，而位置i的数变大，那么就形成了更大的排列（定义）。
        # 2. 因此，只能从位置i后面的位置取更大的数放到位置i来，就不会影响前面的结果，此时位置i越靠右越好。
        # 因此问题的关键是：需要找到位置i，使得位置i后面存在一个刚好比位置i的数大的数，那我们把这个数放到位置i，就使得前面不变，而将位置i的数稍微变大了；然后将后面再排序一下，使得后面构成最小的排列。
        n = len(nums)
        exist = False # 是否存在后面一个数比位置i的数更大
        for i in range(n-1, -1, -1):
            if max(nums[i:]) > nums[i]:
                exist = True
                break
        if not exist: # 如果不存在，意味着整个数组是递减的，反序输出即可。
            return nums[::-1]
        # 寻找后面刚好比nums[i]稍大的那个数的位置minlargej
        minlargej, minlarge = i, float('inf')
        for j in range(i+1, n):
            diff = nums[j]-nums[i]
            if diff > 0 and diff < minlarge:
                minlarge = diff
                minlargej = j
        nums[i], nums[minlargej] = nums[minlargej], nums[i] # 交换一下，使得nums[i]稍微变大
        nums[i+1:] = sorted(nums[i+1:]) # 排序一下后面的数组，形成最小的排列
        return nums

class Solution:
    def nextPermutation(self , nums: List[int]) -> List[int]:
        # write code here
        if len(nums)==1:return nums
        for i in range(len(nums)-1,0,-1):
            if nums[i]>nums[i-1]:
                t = nums[i]
                nums[i] = nums[i-1]
                nums[i-1] = t
                return nums
        return nums[::-1]