LC31　下一个排列¶

中等通过率 43.1%python3核心代码模式技巧样例通过牛客 AC数组双指针

讲解章节：构造

一句话

原地把数组改成字典序恰好比它大一档的那个排列。

解题思路¶

这题考什么¶

「下一个排列」不是随便找个更大的排列，而是所有比它大的排列里最小的那个。要让增幅最小，改动就要尽量靠右——高位一动，增幅至少是一个高位单位，太浪费。

从右往左看，一段非递增的后缀（如 [1, 5, 4, 3, 2] 的 [5, 4, 3, 2]）内部已经是字典序最大的排列，光重排它得不到更大的结果。所以必须往左退到第一个「下坡口」——最靠右的下标 i 满足 nums[i] < nums[i + 1]。退不动（整个数组非递增）就说明当前已是最大排列，题面要求此时重排为升序，即整体翻转。

找到 i 之后分两步：

在后缀 nums[i + 1:] 里挑出大于 nums[i] 的最小值与 nums[i] 交换。这一步让第 i 位涨得最少。因为后缀非递增，从右往左第一个大于 nums[i] 的元素就是这个最小值，不必排序也不必二分。
交换后把后缀翻转成升序。第 i 位已经涨了，后面就要尽可能小；而交换不破坏后缀的非递增性（换进去的 nums[i] 仍夹在原位的合法区间里），所以后缀依旧非递增，翻转一次即得升序，无需真的排序。

整个过程是两次线性扫描加一次翻转，全部原地完成，符合「只允许额外常数空间」。

数据规模与复杂度¶

1 <= nums.length <= 100，0 <= nums[i] <= 100，注意允许重复元素。时间 O(n)、额外空间 O(1)。朴素做法「生成全部排列排序后取下一个」是 O(n! * n)，n = 100 时天文数字，连 n = 12 都跑不动，完全不可行。

坑在哪¶

签名返回 None，答案留在入参里。判题驱动对返回 void 的题会回头读入参（见 scripts/corerun.py 的 call_function），所以必须原地改 nums。写成 nums = sorted(...) 只是把局部名字重新绑定，调用方的列表纹丝不动，判题会拿到未修改的原数组。要改就得用下标赋值或切片赋值。
两次查找的方向都必须是从右往左，找的都是「第一个满足条件的」。从左往右找下坡口会拿到最靠左的那个，改动的位太高，得到的排列比真正的下一个排列大；例如 [1, 3, 2] 从左找会去动下标 0，答案错成 [3, 1, 2]，正确答案是 [2, 1, 3]。
比较必须用严格小于。找下坡口写成 nums[i] <= nums[i + 1]、或在后缀里找 nums[j] >= nums[i]，都会让相等元素参与交换：换了等于没换，后缀翻转后排列反而变小。[1, 1, 5] 是检验这一点的样例。
整个数组非递增时没有下坡口，此时 i 会走到 -1。必须单独处理成「整体翻转为升序」，题面明确规定 [3, 2, 1] 的下一个排列是 [1, 2, 3]。不判这个分支就会用 -1 当下标去索引，悄悄改到数组末尾，结果错得不易察觉。
后缀处理用翻转而不是 sort：交换后后缀仍保持非递增，翻转就是升序， O(n) 完成。用 sort 结果一样但多一个 log 因子，也掩盖了「后缀有序」这个本题最核心的性质。
严格比对：下一个排列唯一，没有多解。

样例复核¶

nums = [1, 5, 4, 3, 2]。从右找下坡口：4 > 3 > 2 一路非递增，退到 i = 0（1 < 5）。在后缀 [5, 4, 3, 2] 里从右找第一个大于 1 的：j = 4（值 2）。交换后：[2, 5, 4, 3, 1]，后缀 [5, 4, 3, 1] 仍非递增。翻转后缀：[2, 1, 3, 4, 5]，正是比 [1, 5, 4, 3, 2] 大的最小排列。 nums = [1, 1, 5]：下坡口 i = 1（1 < 5），后缀 [5] 里第一个大于 1 的是 5，交换得 [1, 5, 1]，后缀只有一个元素翻转不变，输出 [1, 5, 1]，与题面一致。

参考实现¶

solutions/leetcode/LC31/sol.py
from typing import List, Optional


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        # 第一步：从右往左找「下坡口」——最靠右的 i 满足 nums[i] < nums[i + 1]。
        # 它右边那段是非递增的后缀，内部已达字典序最大，只能动到 i 这一位。
        # 必须用严格小于：相等时交换等于没换，翻转后排列反而变小
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        # i == -1 表示整个数组非递增，已是最大排列。
        # 题面规定这时重排为升序，下面的整体翻转正好完成这件事
        if i >= 0:
            # 第二步：在后缀里从右往左找第一个大于 nums[i] 的元素。
            # 后缀非递增，所以从右数第一个满足的就是「大于 nums[i] 的最小值」，
            # 换上去能让第 i 位涨幅最小。同样要严格大于，否则会和相等元素空换
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        # 第三步：把 i 之后的后缀翻转。交换不破坏后缀的非递增性，
        # 翻转一次即得升序，让高位涨过之后的低位尽可能小。
        # i = -1 时这里的起点是 0，退化成整体翻转，正好覆盖上面那个分支
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

LC31 下一个排列¶