力扣百题通

31. 下一个排列 (Medium)

Properties2
description整数数组的一个排列就是将其所有成员以序列或线性顺序排列。
tags12-技巧

10分钟阅读

31. 下一个排列 (Medium)

专题归类： 12-技巧 LeetCode 链接： https://leetcode.cn/problems/next-permutation/

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

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

你必须原地修改，只使用常量额外空间。

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

题目详细分析

数据范围： 1 <= nums.length <= 100，0 <= nums[i] <= 100

核心约束：

  • 原地修改，不能返回新数组
  • O(1) 额外空间，不能用递归或额外数组
  • 如果已经是最大排列（降序），则翻转为最小排列（升序）
  • 数组中可能包含重复元素

关键洞察：

  • 字典序可以理解为”越靠左的数字对大小的影响越大”——就像比较两个数字
  • 要找下一个更大的排列，本质上是要找到”最靠右的”可以变得更小的位置进行调整
  • 标准解法是一个三步走的算法，也是 C++ STL 中 next_permutation 的实现方式：
    1. 从右向左找到第一个升序对（打破降序的位置）
    2. 从右向左找到第一个比该位置大的数
    3. 交换并反转

小白版直白理解

就像你在翻字典找词。如果你在查”123”，下一页是什么？是”132”。为什么？因为你要找”下一个”，就是尽可能小地增大。

具体怎么做？想象一排数字 [1,2,3]：

  1. 从右往左看，找第一个”变小的位置”——3 比 2 大，所以 2 是我们要调整的位置
  2. 在 2 的右边，找一个”比 2 大但尽可能小”的数——就是 3
  3. 交换 2 和 3，得到 [1,3,2]
  4. 然后把原来 2 右边的部分从小到大排好（反转就行，因为原来是从大到小的）

换种生活化的说法：就像你在调节一个密码锁的数字转盘。你要找到下一个合法的排列，就尽量动最右边的数字，让它变大一点点，然后把右边重新排成最小的样子。

解题思路

思路一：标准三步法（推荐）

思路讲解： 算法分为三步：

第一步：找转折点。 从右向左遍历，找到第一个 nums[i] < nums[i+1] 的位置 i。这个位置就是要调整的地方——在此处，升序被打破，说明我们可以通过改变这里的数字得到更大的排列。如果找不到这样的 i，说明整个数组是降序的，已经是最大排列，直接反转整个数组。

第二步：找交换目标。 从右向左找到第一个 nums[j] > nums[i] 的位置 j。这个 nums[j] 是右边比 nums[i] 大的数中最小的那个（因为从右向左第一个大于的就是最小的）。

第三步：交换并反转。 交换 nums[i] 和 nums[j]，然后将 i+1 到末尾的部分反转（因为此时这部分是降序的，反转后变成升序，即为最小的排列）。

def nextPermutation(nums):
    n = len(nums)
    
    # Step 1: 从右向左找第一个升序对 (i, i+1) 满足 nums[i] < nums[i+1]
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    
    # Step 2: 如果找到了这样的 i，从右向左找第一个大于 nums[i] 的数
    if i >= 0:
        j = n - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        # Step 3: 交换
        nums[i], nums[j] = nums[j], nums[i]
    
    # Step 4: 反转 i+1 到末尾（使这部分变成升序/最小排列）
    l, r = i + 1, n - 1
    while l < r:
        nums[l], nums[r] = nums[r], nums[l]
        l += 1
        r -= 1

时间复杂度： O(n) | 空间复杂度： O(1)

思路二：暴力法（用于理解）

思路讲解： 生成所有排列，排序，找到当前排列的下一个。这仅用于理解”下一个排列”的含义，实际不可用。

from itertools import permutations
 
def nextPermutation(nums):
    # 生成所有排列（仅用于理解概念）
    perms = sorted(set(permutations(nums)))
    curr = tuple(nums)
    idx = perms.index(curr)
    if idx < len(perms) - 1:
        nums[:] = list(perms[idx + 1])
    else:
        nums[:] = list(perms[0])

时间复杂度： O(n!) | 空间复杂度： O(n!) | 仅用于理解，不可用于实际

易错点

  • 比较符号的细节：找 i 时用 nums[i] >= nums[i+1]（包含等号），找 j 时用 nums[j] <= nums[i]（包含等号）。包含等号才能正确处理重复元素
  • i 可能为 -1：如果整个数组是降序，i 保持为 -1，此时跳过交换步骤，直接反转整个数组
  • 必须在原地修改 nums：不能 return 新数组，必须直接修改 nums 的内容
  • 反转的范围：反转的是 i+1 到末尾，不是 0 到末尾。仅当 i == -1 时才反转整个数组
  • 重复元素处理：[1,1,5] 的下一个排列是 [1,5,1]，不是 [1,1,5]，算法中的 >= 和 <= 保证了这一点
  • 数组长度为 1：n-2 为 -1，while 循环不执行，i 为 -1，直接反转整个数组（相当于不变）

框架提炼

全排列的字典序下一个模板

def nextPermutation(nums):
    n = len(nums)
    
    # 1. 从右向左找第一个升序对（打破降序的位置）
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    
    # 2. 找到右边比 nums[i] 大的最小数
    if i >= 0:
        j = n - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    
    # 3. 反转 i+1 到末尾（降序变升序）
    l, r = i + 1, n - 1
    while l < r:
        nums[l], nums[r] = nums[r], nums[l]
        l += 1
        r -= 1

核心思想总结：

  1. 找转折点：从右向左找第一个下降的位置 i（即 nums[i] < nums[i+1]）
  2. 找交换对象：在 i 的右边找最小的比 nums[i] 大的数
  3. 交换：让 i 位置的数变大一点点
  4. 反转：让 i 右边的部分变成最小的排列（升序）

记忆口诀：“从右找降，再找大数，交换反转。”

这个模板是 C++ STL next_permutation 算法的本质，可用于：

  • 遍历所有排列（结合循环）
  • 解决排列相关的数学问题
  • 实现上一个排列（prev_permutation，只需反转比较符号）

关联题目

关系图谱