给定一个单词或整数数组，按字典顺序排列找到下一个排列

例如，“gfg”的下一个排列是“ggf”，[1, 2, 3] 的下一个排列是 [1, 3, 2]。

第一步：从后往前找到第一个破坏单调递增性质的位置（i， i+1）

第二步：在 i 后面找到位置最靠后比 A[i] 大的元素A[j]

第三步：交换 A[i] 和 A[j]

第四步：从 (i+1) 位置开始颠倒序列

def nextPermutation(nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    
    n = len(nums)
    
    # step 1: find the larget i, such that A[i] < A[i+1]
    found = False
    for i in range(n-2, -1, -1):
        if nums[i] < nums[i+1]:
            found = True
            break
    # Notice: if can't find any, we have the largest permutation
    if not found: return nums.reverse()
    
    # step 2: find the largest index j, such that A[i] < A[j]
    for k in range(i+1, n):
        if nums[i] < nums[k]:
            j = k
    
    # step 3: swap i and j
    nums[i], nums[j] = nums[j], nums[i]
    
    # step 4: reverse A[i+1] to the end
    for k in range(i+1, (i+n)//2+1):
        nums[k], nums[n+i-k] = nums[n+i-k], nums[k]
    
    return nums

Follow-up: 怎样找前一个排列呢？