31. 下一个排列

LeetCode 31¹ · 中等 · 技巧

题

把整数数组 nums 原地改成字典序里紧挨着的下一个排列；已经是最大的（整体降序），就变回最小的（整体升序）。只能用常数额外空间。

例：[1, 2, 3] → [1, 3, 2]；[3, 2, 1] → [1, 2, 3]；[1, 1, 5] → [1, 5, 1]。

一句话

找最右边能变大的位置 i（nums[i] < nums[i+1]），把它换成右边比它大的数里最小的那个，再让右边变成最小——升序。

关键技巧

要「变大」，且变得最少。 字典序比大小看最左边不同的位置，所以想增幅最小，改动的位置要尽量靠右。

第一步：找下降点。 从右往左找第一个 nums[i] < nums[i+1] 的 i。i 右边是一段非增序列——它已经是这几个数能排出的最大排列，只动右边不可能变大，必须动 i。找不到 i 说明整体非增，已是最大排列。

第二步：换一个刚好大一点的。 在 i 右边找比 nums[i] 大的数里最小的那个。右段非增，所以从右往左第一个 > nums[i] 的 j 就是它。交换后 nums[i] 增幅最小。

第三步：右边归零。 交换后右段仍然非增（nums[j] 换成了更小的 nums[i]，但它仍 ≥ 右侧、< 左侧，顺序不破）。把它反转成非降序，就是最小的后缀——不用排序，反转即可，\(O(n)\)。

整体降序时统一处理。 i = -1 时跳过交换，直接反转整段，最大排列变成最小排列。

解

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:  # 找下降点
            i -= 1
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:             # 右段非增，从右找第一个更大的
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        l, r = i + 1, n - 1                        # 右段反转成升序
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l, r = l + 1, r - 1

时间 \(O(n)\)，空间 \(O(1)\)。

延伸

• 生成全部排列：46. 全排列 用回溯；从最小排列反复调用本题也能按字典序生成全部，且天然去重（有重复元素时）。
• 第 k 个排列（LeetCode 60）：康托展开，逐位按阶乘确定，不用一步步跳。
• 坑：两处比较都要带等号（>=、<=），否则 [1, 5, 1]、[1, 1] 这类含重复的会出错或越界。

s = Solution()
for arr, want in [
    ([1, 2, 3], [1, 3, 2]),
    ([3, 2, 1], [1, 2, 3]),
    ([1, 1, 5], [1, 5, 1]),
    ([1], [1]),
    ([1, 3, 2], [2, 1, 3]),
    ([1, 5, 1], [5, 1, 1]),
    ([2, 2], [2, 2]),
]:
    s.nextPermutation(arr)
    assert arr == want