下一个排列

31. 下一个排列 - 力扣（LeetCode）

问题简述

给定一个整数数组，求该数组的下一个排列。
注意：完全逆序的下一个排列是正序。
要求：原地修改数组。

思路

• 为了使下一个排列更大，一个方法是将一个左边的「较小数」与一个右边的「较大数」交换；而为了使变大的幅度最小，需要让这个「较小数」尽量靠右，而「较大数」尽可能小。

• 具体实现：

  1. 找左边界：从后往前遍历，找到第一个 l 使 a[l] 小于 a[l + 1]，此时必有 a[l+1:] 为逆序；

  2. 找右边界：再次从后往前遍历，找到第一个大于 a[l] 的位置 r；因为 a[l+1:]，所以 j 依次遍历即可，此时 a[l+1:] 依然为逆序；

  3. 交换 a[l] 和 a[r]；

  4. 将 a[l+1:] 倒序；

• 第 4 步说明：

  • 在第 3 步交换 a[l] 和 a[r] 后，无论 a[l+1:] 无论怎么调整，都是比原来更大的排列，而其中最小的排列就是 a[l+1:] 为顺序的情况，又因为此时 a[l+1:] 正好为逆序，所以将其做倒置即可；

Python

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if (L := len(nums)) < 2:
            return 
        # 1.
        l = len(nums) - 2
        while l >= 0 and nums[l] >= nums[l + 1]:  # 因为要找 nums[l] < nums[l + 1]，所以这里是 >=
            l -= 1
        # 2.
        if l >= 0:
            r = L - 1
            while r > 0 and nums[r] <= nums[l]:  # 同理要找 nums[r] > nums[l]，所以这里是 <=
                r -= 1
            # 3.
            nums[l], nums[r] = nums[r], nums[l]
        # 4.
        nums[l+1:] = nums[l+1:][::-1]

提示：

• 这里要求完全逆序的下一个排序是正序；

• 如果取消这个要求，那么当找到 l < -1 时，退出即可，此时说明整个数组时逆序的；