LC 31下一个排列Next Permutation　中等

把数组原地重排成字典序的下一个更大排列；不存在时重排为最小的排列。

思路 标准四步：从右找第一个升序位置 i；再从右找第一个大于 nums[i] 的 j 交换；最后反转 i+1 到末尾。时间 O(n)。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = reversed(nums[i + 1:])