給定一個(gè)單詞或整數(shù)數(shù)組，按字典順序排列找到下一個(gè)排列

例如，“gfg”的下一個(gè)排列是“ggf”，[1, 2, 3] 的下一個(gè)排列是 [1, 3, 2]。

第一步：從后往前找到第一個(gè)破壞單調(diào)遞增性質(zhì)的位置（i， i+1）

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

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

第四步：從 (i+1) 位置開(kāi)始顛倒序列

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: 怎樣找前一個(gè)排列呢？