31.md

题目地址

https://leetcode-cn.com/problems/next-permutation/

解答

def nextPermutation(nums):
    """
    下一个排列

    Do not return anything, modify nums in-place instead.

    因为是字典序排列，所以当一个排列不是完全逆序排列时，总可以将其重新排列使其字典序更大。 所以我们可以将一个排列分成左右两部分。
    右边的是一个完全逆序排列，左边剩余的部分称为前缀。 像这样：

    [a_1, a_2, ..., a_j-1] + [a_j, ..., a_n]

    根据前缀的长度可以分为两种情况，
    1、前缀为空列表 []
    2、前缀非空

    第一种情况，直接逆转整个列表即可。

    需要讨论的是第二种情况。

    首先注意到，若将前缀最后一个数添进右边部分，则右侧不再是完全逆序排列。因此可以对其进行重新排列使其字典序更大。根据题意，
    a_j-1只能被右侧大于它的最小数替换。替换后，新的右侧仍然是完全逆序排列。但是根据题意，新的右侧应该是升序排列，所以将其逆转即可。

    """
    n = len(nums)
    i = n - 1
    # = 号表示可以处理存在重复数字的情况
    while i and nums[i - 1] >= nums[i]:
        i -= 1
    if i:
        # 前缀不为空，nums[i]是右侧完全逆序排列的第一个数
        # nums[pre] 是前缀的最后一个数
        pre = i - 1
        j = i
        while j < n - 1 and nums[j + 1] > nums[pre]:
            j += 1
        # nums[j] 是右侧大于nums[pre] 的最小值
        nums[pre], nums[j] = nums[j], nums[pre]
    # 逆转右侧为升序排列
    j = n - 1
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1