企业官网建设流程全解析

LeetCode 31. 下一个排列（Next Permutation）题解：原地 O(n) 求字典序后继的贪心算法

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇技术指南以本仓库（leetcode 解题之路）中 problems/31.next-permutation.md 为核心，完整拆解 LeetCode 第 31 题「下一个排列」：从回溯视角推导出"从后往前找第一个递减位置 + 右侧最小更大值交换 + 尾部反转"的线性算法，并给出 JavaScript、Python3、CPP 三种可运行实现。读完本文，你将掌握字典序排列后继问题的标准解法、其与全排列（46/47）、第 k 个排列（60）等排列家族题目的关系，以及如何写出时间复杂度 O(n)、空间复杂度 O(1) 的原地解法。

题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列：

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

三个例子分别覆盖了三种典型场景：普通递增序列（交换相邻元素即得后继）、完全递减序列（不存在后继，需返回升序最小排列）、含重复元素的序列（说明算法必须正确处理重复值）。

题目有两个硬性约束，直接决定了算法选型：

• 必须原地修改：只能操作传入的nums数组，不能新建数组再整体赋值；
• 只允许使用额外常数空间：排除一切需要 O(n) 辅助空间的方案。

前置知识与考察点

本题虽被归类为中等难度（仓库 collections/medium.md 中亦有收录），但考察的知识点相当综合：

• 回溯法：仓库 thinkings/backtrack.md 指出，回溯本质是穷举所有可能的试错过程，可抽象为一棵 N 叉树，全排列问题的解空间大小是 n!。虽然本题最终用贪心 + 双指针解决，但回溯思维是理解"下一个排列"语义的钥匙；
• 贪心思想：要得到"下一个更大的排列"且增幅最小，需要选取恰当的交换对象；
• 双指针 / 反转：在有序区间内用首尾交换实现反转，是本题收尾步骤的核心技巧。

核心思路：从暴力回溯到字典序后继

为什么暴力生成全排列不可行

符合直觉的方法是按顺序求出所有的排列（参考 problems/46.permutations.md 中的回溯实现），如果当前排列等于nums，直接取下一个。但这种做法有两个致命问题：

1. 时间复杂度为O(n!)，n 稍大即不可接受；
2. 需要把整个排列空间保存在结果集中，不符合 constant space（常数空间）的要求——题目要求直接修改原数组。

因此必须寻找不依赖全排列枚举的定向构造方法。

回溯视角：从后往前思考

我们可以以回溯的角度来思考这个问题，即从后往前思考。回溯的本质是逐步尝试每个位置可以放置的数字，当我们走到最后一个数字时，如果它无法构成更大的排列，就"退回"上一步尝试其他选择。

让我们先回溯一次，即思考最后一个数字是如何被添加的：

由于这个时候可以选择的元素只有 2，我们无法组成更大的排列，我们继续回溯，直到如图：

我们发现可以交换 4 和 2，但这样会变小，因此我们不能进行交换。

接下来碰到了 1，我们有两个选择：

• 1 和 2 进行交换；
• 1 和 4 进行交换。

两种交换都能使得结果更大，但是和 2 交换能够使得增值最小，也就是题目要求的"下一个更大的排列"效果。因此我们将 1 和 2 进行交换：

贪心：为什么交换低位而不是更高位

还需要继续往高位看么？不需要，因为交换高位得到的增幅一定比交换低位大，这是一个贪心的思想——要得到"下一个更大的排列"，增幅越小越好，因此我们应该优先在尽可能低（靠右）的位置上做文章，而不是轻易动高位。

关键洞察：第一个可交换的回溯点就是"从后往前第一个递减的值"

从上面的回溯过程可以提炼出本题最核心的洞察：

从后往前扫描，找到第一个满足nums[i] < nums[i + 1]的位置i，这个i就是"第一个可以交换的回溯点"。

为什么？因为i右侧的所有元素构成一个从后往前非递减的序列（即非严格递减），此时右侧已经没有任何内部交换能产生更大排列，只能把更高位的nums[i]换掉。从代码结构看（详见下文实现），一旦i不存在，说明整个数组本身已经是从大到小的最大排列，此时直接反转整个数组得到升序最小排列即可。

如何保证增幅最小

交换时，需要在i右侧找到"从右边起第一个大于nums[i]的数"（即大于nums[i]的最小值）与之交换——因为如果交换的数字比nums[i]还小，结果会变小，不符合题意。

交换完成后，还需要保证i右侧的序列是升序（最小的字典序）。注意到i后面的数在交换前已经是从大到小排列（非严格递减），交换后依然保持递减序，此时我们只需要用双指针首尾交换（reverse）即可，而不需要真正地排序。

补充证明：i后面的数一定是从大到小排好序了吗？当然，否则，我们找到第一个可以交换的回溯点就不是i了，和i是第一个可以交换的回溯点矛盾。因为第一个可以交换的回溯点其实就是从后往前第一个递减的值。这一性质保证了尾部区间用双指针反转即可完成升序化，复杂度从 O(n log n) 降至 O(n)。

算法步骤（逐步分解）

综上，标准解法可归纳为四步：

1. 找分割点：从后往前扫描，找到第一个满足nums[i] < nums[i + 1]的位置i；
2. 判是否最大排列：若i < 0，说明整个序列是递减的（已是最大排列），跳到第 4 步直接整体反转；
3. 交换：从右往左找到第一个大于nums[i]的位置j，交换nums[i]与nums[j]；
4. 反转尾部：将[i + 1, len - 1]区间的元素反转（升序化），得到字典序意义上的"下一个最小更大排列"。

以1,2,3为例走一遍：从后往前找到i = 1（nums[1] = 2 < nums[2] = 3），右侧第一个大于 2 的是 3，交换得1,3,2，再反转[2,2]区间（单元素无需操作），结果为1,3,2，与题目示例一致。

以3,2,1为例：找不到任何nums[i] < nums[i + 1]，即i = -1，直接整体反转得1,2,3，与题目示例一致。

三种语言实现

原文档提供了 JavaScript、Python3、CPP 三种实现，以下代码可直接复制运行，均满足原地修改与常数空间约束。

JavaScript

/* * @lc app=leetcode id=31 lang=javascript * * [31] Next Permutation */ function reverseRange(A, i, j) { while (i < j) { const temp = A[i]; A[i] = A[j]; A[j] = temp; i++; j--; } } /** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ var nextPermutation = function (nums) { // 时间复杂度O(n) 空间复杂度O(1) if (nums == null || nums.length <= 1) return; let i = nums.length - 2; // 从后往前找到第一个降序的,相当于找到了我们的回溯点 while (i > -1 && nums[i + 1] <= nums[i]) i--; // 如果找了就swap if (i > -1) { let j = nums.length - 1; // 找到从右边起第一个大于nums[i]的，并将其和nums[i]进行交换 // 因为如果交换的数字比nums[i]还要小肯定不符合题意 while (nums[j] <= nums[i]) j--; const temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } // 最后我们只需要将剩下的元素从左到右，依次填入当前最小的元素就可以保证是大于当前排列的最小值了 // [i + 1, A.length -1]的元素进行反转 reverseRange(nums, i + 1, nums.length - 1); };

Python3

class Solution: def nextPermutation(self, nums: List[int]) -> None: i = len(nums) - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i >= 0: j = len(nums) - 1 while j >= 0 and nums[i] >= nums[j]: j -= 1 nums[i], nums[j] = nums[j], nums[i] left, right = i + 1, len(nums) - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1

CPP

class Solution { public: void nextPermutation(vector<int>& nums) { int i = nums.size() - 2, j = nums.size() - 1; while (i >= 0 && nums[i] >= nums[i + 1]) --i; if (i >= 0) { while (j > i && nums[j] <= nums[i]) --j; swap(nums[i], nums[j]); } reverse(nums.begin() + i + 1, nums.end()); } };

代码细节对照

值得注意的是i = -1（最大排列）时，reverseRange(nums, 0, len - 1)恰好将整个数组反转回升序最小排列，因此三种实现都不需要为"不存在后继"单独分支处理反转范围——这一设计非常精妙。

复杂度分析

令n为数组长度：

• 时间复杂度：O(n)。扫描分割点最坏 O(n)，找交换点最坏 O(n)，尾部反转 O(n/2)，三个线性步骤顺序执行，总复杂度为 O(n)；
• 空间复杂度：O(1)。只使用常数个索引变量与临时交换变量，完全符合题目"只允许使用额外常数空间"的约束。

这一结论可直接从代码结构验证：全程无递归、无辅助数据结构，仅有i、j与temp三个标量。

边界情况与重复元素处理

本题的边界情况很容易出错，务必用多组数据自测：

1. 单元素 / 空数组：nums == null || nums.length <= 1时直接返回，无需任何操作；
2. 完全递减（最大排列）：如3,2,1，找不到分割点，整体反转得到升序最小排列；
3. 含重复元素：如1,1,5 → 1,5,1、1,5,1 → 5,1,1。关键在于扫描时使用<=（非严格）比较，使分割点落在相等区间的最左侧，交换时同样用<=跳过相等值，保证重复元素下仍能得到字典序紧邻的后继；
4. 交换后尾部仍需反转：交换只保证nums[i]变大，若尾部仍为递减序，必须反转才能得到"最小更大排列"。

与排列家族题目的横向对比

仓库中围绕"排列"有一组互相呼应、层层递进的题目，理解本题后建议串联学习：

其中 problems/60.permutation-sequence.md 的这段归类说明（"LeetCode 上关于排列的题目目前主要有三种类型"）非常值得阅读，它揭示了这三类题目在解空间上的递进关系：全排列枚举解空间 → 在解空间中定位紧邻后继 → 在解空间中按序数直接构造。

关键点总结

原文档对本题给出了三条凝练的经验，这也是面试复盘时的高频考点：

• 写几个例子通常会帮助理解问题的规律：比如把1,2,3的全排列按字典序写出，观察相邻两项的变化规律，规律自然浮现；
• 在有序数组中首尾指针不断交换位置即可实现 reverse：这是反转区间的高效手法，时间复杂度 O(n)、空间 O(1)，比sort更适合本题的降序尾部；
• 找到从右边起第一个大于nums[i]的数，并将其和nums[i]进行交换：这是保证"增幅最小"的关键，交换对象必须是右侧大于nums[i]的最小值。

此外，仓库还提供了本题的可视化资源：assets/drawio/31.next-permutation.drawio（draw.io 流程图），以及本文沿用的 assets/problems/31.next-permutation-2.jpg、assets/problems/31.next-permutation-3.jpg、assets/problems/31.next-permutation-4.jpg 三张过程示意图，适合配合本文章反复推演。

延伸思考

• 若题目要求改为"上一个排列"，只需把算法中的大小比较全部反向（找从后往前第一个递增点、交换右侧最大更小值），即可对称地解决；
• 本题的 O(n) 线性复杂度来源于尾部区间的"非严格递减"性质，这个性质是回溯推导的直接推论——理解推导过程比背代码更重要；
• 实际工程中，"字典序后继"思想还被用于生成组合、子集等对象的全量枚举（如 next_combination 类算法），掌握本题的思维框架后可以触类旁通。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode