跳到主要内容

0031. 下一个排列

题目描述​

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3]，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2]。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2]。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3]，因为 [3,2,1] 不存在一个字典序更大的排列。

必须 原地 修改，只允许使用额外常数空间。

解题思路​

第一步：理解问题本质​

"下一个排列"的本质是：在所有可能的排列中，找到比当前排列字典序恰好大一点的那个。

字典序的比较方式与字典里单词的排序类似：从左往右逐位比较，第一个不同的位置决定大小。比如 [1,3,2] 比 [1,2,3] 大，因为第二位 3 > 2。

关键观察：一个排列如果从右向左看是严格递增的（如 [...5, 4, 3, 2, 1] 的后缀），那这段后缀已经是最大排列，无法通过内部调整变得更大。我们必须改动更左边的数字才能让整体变大。

第二步：暴力解法​

最直接的想法：生成当前排列之后的所有排列，取紧接着的那个。

from itertools import permutations

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        perms = sorted(set(permutations(nums)))
        idx = perms.index(tuple(nums))
        if idx + 1 < len(perms):
            nums[:] = list(perms[idx + 1])
        else:
            nums[:] = list(perms[0])

为什么不够好：

  • 生成所有排列需要 O(n!) 时间和空间，n 稍大就会超时。
  • 对于 n=10，排列数量高达 3,628,800，远远超出实际需要。

第三步：最优解法——三步法（原地 O(n)）​

核心思路：不需要生成所有排列，只需要在原数组上做三个局部操作。

为什么这三步是正确的？

想象数组 [1, 3, 5, 4, 2]，从右往左看后缀 [5, 4, 2] 是严格递减的，这意味着这段后缀已经是最大排列。继续往左看，3 比 5 小，说明 3 是第一个"还有上升空间"的位置，也就是下降点。

要让整个排列只增大一点点，策略是：

  1. 把下降点的数换成它右边比它大但尽量小的数（让变化尽可能小）。
  2. 换完之后，下降点右边的所有数变成升序（因为原来是降序，只需要反转），保证后缀尽量小。

三步骤详解：

第一步——找下降点 i：从右向左扫描，找到第一个满足 nums[i] < nums[i+1] 的位置 i。这个位置就是"右边已经达到最大，需要修改这里"的临界点。若找不到（整个数组单调递减），说明当前是最大排列，跳过第二步，直接执行第三步（反转整个数组变为最小排列）。

第二步——找替换数 j：在 i 右边（已经是降序），从右向左找第一个满足 nums[j] > nums[i] 的位置 j，交换 nums[i] 和 nums[j]。从右往左找是为了找到比 nums[i] 大但尽量接近它的数，让变化最小。

第三步——反转后缀：交换完成后，i+1 到末尾的部分仍然是降序（交换只改变了两个元素的相对位置，且新的 nums[i] 更大，右边仍保持降序），将其反转变为升序，使后缀取到最小值。

完整代码实现​

from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        原地修改，不返回值
        """
        n = len(nums)

        # 第一步：从右向左找下降点 i（nums[i] < nums[i+1]）
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        # 第二步：若找到下降点，从右向左找最小的比 nums[i] 大的数 j，交换
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        # 第三步：反转 i+1 到末尾，使后缀变为最小（升序）
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

示例推演​

以 nums = [1, 3, 5, 4, 2] 为例，逐步演示：

初始状态：[1, 3, 5, 4, 2]，n = 5

第一步：找下降点 i

从 i = 3 开始向左扫描：

  • i = 3：nums[3]=4，nums[4]=2，4 >= 2，继续左移
  • i = 2：nums[2]=5，nums[3]=4，5 >= 4，继续左移
  • i = 1：nums[1]=3，nums[2]=5，3 < 5，停止，下降点 i = 1

第二步：找替换数 j

在 i=1 右边（即 [5, 4, 2]），从 j=4 向左找第一个大于 nums[1]=3 的数：

  • j = 4：nums[4]=2，2 <= 3，继续左移
  • j = 3：nums[3]=4，4 > 3，停止，j = 3

交换 nums[1] 和 nums[3]：[1, 3, 5, 4, 2] → [1, 4, 5, 3, 2]

第三步：反转 i+1=2 到末尾

反转 [5, 3, 2]（索引 2 到 4）：

  • 交换 nums[2] 和 nums[4]：[1, 4, 2, 3, 5]
  • left=3, right=3，left 不小于 right，停止

最终结果：[1, 4, 2, 3, 5]

验证：[1,3,5,4,2] 的所有排列中，[1,4,2,3,5] 确实是它的下一个排列。

再看边界情况：nums = [3, 2, 1]（完全降序，当前是最大排列）

第一步：i 从 1 开始，nums[1]=2 >= nums[2]=1，继续；nums[0]=3 >= nums[1]=2，继续；i 减到 -1，未找到下降点。

第二步：i < 0，跳过。

第三步：反转整个数组（left=0, right=2）：[3,2,1] → [1,2,3]

最终结果：[1, 2, 3]，即最小排列。

复杂度分析​

解法时间复杂度空间复杂度说明
暴力（生成全排列）O(n!)O(n!)枚举所有排列后取下一个
三步法（最优）O(n)O(1)三次线性扫描，原地操作

易错点总结​

  • 找下降点时用 >= 而非 >：当 nums[i] == nums[i+1] 时，这段后缀并非严格递减，但仍需继续左移。若用 >，相等时会提前停止，导致错误。

  • 找替换数时从右往左：右边是降序排列，从右边找到的第一个大于 nums[i] 的数，保证是"最小的更大数"，从而让排列只增大最少一点。

  • 第三步一定要反转：交换完成后，i+1 到末尾依然是降序，反转变为升序才能保证后缀最小，进而保证整体排列字典序只比原来大一步。

  • i=-1 时仍要执行反转：整个数组是降序时，i 最终为 -1，第三步的 left = i+1 = 0，反转整个数组，使其变为升序（最小排列），这是正确行为。

扩展思考​

  • LeetCode 46. 全排列：生成所有排列，可以用回溯实现，与本题互补。
  • LeetCode 60. 排列序列：给出排列的字典序编号，直接找到第 k 个排列，需要利用阶乘数系统。
  • 算法本质：本题的三步法本质上是在有序序列上的贪心操作——在尽量靠右的位置做尽量小的改变，再把右边变为最小状态。这种"局部贪心"思想在很多字典序问题中都有应用。
加载评论中...