深入解析下一个排列算法：字典序与原地修改

1. 项目概述与核心需求解析

1.1 “下一个排列”到底是什么

第一次在LeetCode上遇到“下一个排列”这道题时，我其实有点懵。因为“排列”这个词在高中数学里就学过，但题目要求的东西，跟我想象中那种全排列输出的场景完全不同。

题目是这么描述的：给定一个整数数组，比如[1,2,3]，要求把它重新排列成字典序中下一个更大的排列。如果当前排列已经是字典序中最大的那个，就把数组重新排列成最小的排列（即升序排列）。

什么叫做“字典序中下一个更大的排列”？说白了，就是把数组看成一个数字，找到用同样这几个数字能组成的、比当前数字大、但又是所有比当前数字大的结果里最小的那一个。拿[1,2,3]举例，用1、2、3能组成的排列按从小到大排是：

123, 132, 213, 231, 312, 321

[1,2,3]对应的就是123，它的“下一个排列”就是132，也就是[1,3,2]。如果当前是[3,2,1]（321），已经是最大，那下一个排列就绕回最小的123，即[1,2,3]。

这道题在LeetCode上是第31题，难度标为“中等”。但说实话，第一次自己啃的时候，我觉得它比很多标着“困难”的题更难理解——因为它的核心不在于代码量，而在于那个“从右往左找拐点”的思维，一旦想通了，代码也就十行以内的事。

1.2 题目限制与输入输出约定

这道题对实现有两个硬性约束，很多人在面试时会忽略：

• 必须原地修改数组，不能额外开一个新数组来装结果；
• 只能使用常数额外空间。

也就是说，你不能先把数组复制一份做全排列排序，再取下一个。这直接把暴力法堵死了。

输入是一个整数数组，长度在1到100之间。输出同样是这个数组，只不过内容被原地重排了。举个例子：

输入: [1,2,3] 输出: [1,3,2]

输入: [3,2,1] 输出: [1,2,3]

输入: [1,1,5] 输出: [1,5,1]

第三个例子很有代表性，它含有重复元素。重复元素存在时，排列的大小比较仍然按照字典序规则，但因为数字相同，结果会少很多。这也是后面容易踩坑的地方——很多人在处理重复元素时，会把“下一个更大的排列”做成“下一个不相同的排列”，结果算出错误答案。

1.3 谁会需要这个算法

别以为这道题只是为了面试刷题，它的应用场景其实比想象中广泛得多：

• 全排列生成：如果你需要按字典序枚举所有排列，每次调用一次“下一个排列”，就能从初始状态一路走到终点，不需要递归，不需要回溯，也不需要额外栈空间。
• 竞赛编程：像一些组合优化、搜索剪枝问题，需要按字典序遍历状态空间，这个算法是标准工具。
• 标准库实现：C++ 的std::next_permutation底层核心思路就是它，理解这道题等于理解了标准库的一个经典实现。
• 业务里的排班、选品组合：凡是涉及到“按字典序找下一个组合/排列”的场景，这个思路都能直接迁移。

所以不管你是准备面试，还是在写一些需要组合枚举的工具类代码，把这道题吃透，收益是长期的。

2. 整体思路拆解：为什么不能暴力枚举

2.1 暴力法为什么会炸

面对“下一个排列”这个问题，最直觉的思路是这样的：

1. 生成这个数组能组成的全部排列；
2. 按字典序排序；
3. 找到当前排列的位置；
4. 取它的下一个。

这个思路正确吗？正确。可行吗？不可行。

原因很简单：n个不同数字的全排列共有n!个。n=10时是三百多万，n=12时已经接近五亿。而题目里数组长度上限是100，100!是个大到没有任何计算机能枚举完的数字。你连枚举都枚举不完，更谈不上排序和查找了。

所以这道题真正想考察的不是“你会不会全排列”，而是“你懂不懂字典序排列的结构规律”。排列之间不是散乱分布的，它们之间有一条隐藏的序关系，找到这个序关系，就能直接算出来，而不是“生成所有再找”。

2.2 字典序排列的递增规律

要理解“下一个排列”怎么求，得先理解排列之间的大小是怎么比较的。

字典序比较规则很简单：从左往右，逐位比较，第一个不同数字的大小决定了两个排列的大小。比如[1,3,2]和[2,1,3]，第一位1比2小，所以前者小于后者。

那如果让整个序列严格递增下去，什么情况下会发生“进位”式的跳变？

仔细观察从[1,2,3]到[1,3,2]这个变化：前1位没变，从第2位开始，由“2,3”变成了“3,2”。也就是说，只动后缀就能找到下一个排列，是因为当前排列的后缀已经是某种有序状态。

再看[1,3,2]到[2,1,3]：这次连第一位都变了，从1变成2。原因是，从[1,3,2]这个排列看，它已经是“1开头的所有排列里最大的一个”（因为后缀3,2是降序，是最大排列）。所以想找下一个更大排列，1这个前缀已经到头了，必须换一个更大的首位数字，然后把剩余后缀排成最小。

对，核心信号就是“降序后缀”。当一个排列的后缀是降序时，说明这个前缀已经撑到最大了，必须进位。

2.3 关键观察：从右往左找第一个“上升点”

基于上面的规律，可以得到一个非常优雅的算法流程：

1. 从右往左遍历数组，找到第一个满足a[i] < a[i+1]的位置i。这个位置就是“拐点”。
2. 如果找不到这样的i，说明整个数组是降序的，也就是最大排列，直接反转整个数组得到最小排列。
3. 如果找到了i，再次从右往左找到第一个大于a[i]的数字a[j]。
4. 交换a[i]和a[j]。
5. 把i+1到末尾这一段反转，让它变成升序（也就是最小排列）。

为什么第一步一定要从右往左找？因为我们要找的是“尽可能靠右的拐点”。只有拐点越靠右，改动的前缀越短，得到的排列才越是“下一个”——它保证增幅最小。

为什么第二步找a[j]也是从右往左？因为从右侧找第一个大于a[i]的数字，这个数字就是“比a[i]大但尽可能小”的候选，交换完之后，后缀仍然保持降序，反转后就能得到最小的后缀。

这两个“从右往左”是整个算法的灵魂，缺一不可。

3. 核心细节解析与实操要点

3.1 每一步操作的底层原理

先手动模拟一个稍长一点的例子，比如[1,5,8,4,7,6,5,3,1]，一步步拆解。

第一步：找拐点。

从右往左扫：

• 1 < 3？不对，1比3小，等等——从右往左，先比较a[7]=3和a[8]=1，3 > 1，不满足；
• 再往前，a[6]=5和a[7]=3，5 > 3，不满足；
• a[5]=6和a[6]=5，6 > 5，不满足；
• a[4]=7和a[5]=6，7 > 6，不满足；
• a[3]=4和a[4]=7，4 < 7，满足。

所以i = 3，a[3] = 4。此时，从i+1到末尾的部分[7,6,5,3,1]是一个严格降序序列。

为什么这个降序序列很重要？因为它意味着“以[1,5,8,4]为前缀的排列已经穷尽了所有可能”。任何对这个前缀的微调，比如把某一位变大，都会产生更大的排列；但我们现在要的是“最小增幅”，所以要尽量保持前缀不动，或者只动最后一位可能的位置。

第二步：从右往左找第一个大于a[i]的数。

从数组末尾开始扫：

• a[8]=1，不大于4；
• a[7]=3，不大于4；
• a[6]=5，大于4，找到了。

所以j = 6，a[j] = 5。

这里注意：因为i+1之后是降序的，从右往左扫其实就是从“最小的元素”往“最大的元素”扫，第一个大于a[i]的数，一定是所有大于a[i]的数里最小的那个。这保证了交换后前缀的增幅是最小的。

第三步：交换a[i]和a[j]。

交换后数组变成[1,5,8,5,7,6,4,3,1]。

这里有个小细节：交换后，i+1到末尾这一段[7,6,4,3,1]仍然是降序的。为什么？因为a[j]是从右往左第一个大于a[i]的数，它右边的数全部小于等于a[i]，所以把a[i]这个较小的值换到j的位置后，它不会打破右侧的降序性质——右侧本来就是降序，且这些数现在都更小了，降序依然成立。

第四步：反转i+1到末尾。

把[7,6,4,3,1]反转为[1,3,4,6,7]，最终得到：

[1,5,8,5,1,3,4,6,7]

这一步为什么用反转而不是排序？因为刚才说过，这一段保持了降序，反转就是升序，也就是后缀能组成的最小排列。这里如果调用排序，逻辑上没错，但会引入O(k log k)的复杂度，而反转是O(k)，而且代码更简洁。

3.2 边界情况与特殊用例

情况一：数组长度为1。

比如[1]。从右往左找，只有一个元素，不存在a[i] < a[i+1]，于是直接反转整个数组，反转后还是[1]。

情况二：数组已经是降序（最大排列）。

比如[3,2,1]。从右往左找不到任何a[i] < a[i+1]，直接反转整个数组得到[1,2,3]。这正好对应题目里说的“如果不存在下一个更大的排列，则重新排列成最小的排列”。

情况三：所有元素都相同。

比如[2,2,2]。从右往左找，2 < 2不成立，所以直接反转，结果还是[2,2,2]。这其实是降序情况的一种特殊形态。

情况四：数组本身已经升序。

比如[1,2,3,4]。从右往左找，第一个满足条件的是i=2（因为3 < 4）。再找大于3的数，从右往左第一个是4。交换[1,2,4,3]，然后反转下标3之后的空区间，得到[1,2,4,3]。结果是正确的，因为1234的下一个排列确实是1243。

3.3 复杂度分析与空间使用

时间复杂度是O(n)：第一步扫描最多走遍全数组，第二步扫描最多也是从头到尾，反转也是一次线性操作。三个线性操作加起来还是O(n)，而且没有嵌套循环。

空间复杂度是O(1)：全程只用了几个临时变量（存下标和交换用的中间值），没有额外数组，完全满足题目“常数额外空间”的要求。

这也是为什么这道题经典：它用最小的代价，实现了全排列字典序枚举的“单步推进”。

4. 实操过程与完整代码实现

4.1 一种通用实现模板

这道题我已经用多种语言写过，这里分享一个跟语言无关的伪代码模板，然后再给C++和Python的具体实现。

function nextPermutation(nums): i = len(nums) - 2 while i >= 0 且 nums[i] >= nums[i+1]: i = i - 1 if i >= 0: j = len(nums) - 1 while j >= 0 且 nums[j] <= nums[i]: j = j - 1 交换 nums[i] 和 nums[j] 反转 nums[i+1:]

注意两个细节：

• 第一步的循环条件是nums[i] >= nums[i+1]，不是>。必须把等于的情况也跳过，否则遇到重复元素时，会把相等元素误判成拐点。
• 第二步的循环条件是nums[j] <= nums[i]，同样要跳过等于的情况。我们要找的是严格大于nums[i]的数。

4.2 C++ 实现

class Solution { public: void nextPermutation(vector<int>& nums) { int n = nums.size(); int i = n - 2; // 从右往左找到第一个升序对 while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { int j = n - 1; // 从右往左找到第一个大于 nums[i] 的数 while (j >= 0 && nums[j] <= nums[i]) { j--; } swap(nums[i], nums[j]); } // 反转 i+1 到末尾 reverse(nums.begin() + i + 1, nums.end()); } };

4.3 Python 实现

def nextPermutation(nums): i = len(nums) - 2 # 从右往左找第一个升序对 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i >= 0: j = len(nums) - 1 # 从右往左找第一个大于 nums[i] 的数 while j >= 0 and nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i] # 反转 i+1 到末尾 left, right = i + 1, len(nums) - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1

4.4 一个完整的手动模拟用例

用[1,5,1]来模拟一遍完整流程：

1. 从右往左找：比较5和1，5 > 1，不满足；比较1和5，1 < 5，满足，所以i = 0。
2. 从右往左找第一个大于nums[0]=1的数：末尾是1，等于1不算；再看5，5大于1，所以j = 1。
3. 交换nums[0]和nums[1]：得到[5,1,1]。
4. 反转i+1=1到末尾：[1,1]反转为[1,1]，最终结果是[5,1,1]。

验证一下：用数字1和5组成的排列，按字典序排是115, 151, 511。151的下一个确实是511，正确。

4.5 为什么这个实现能处理重复元素

重复元素的核心问题在于“排列去重”。还拿[1,1,5]举例，如果第一步循环条件写成>，那么从右往左看，1 > 5不成立，1 > 1也不成立，于是i会一直退到-1，直接执行反转，得到[5,1,1]，这是错误的。正确结果应该是[1,5,1]。

问题出在nums[i] >= nums[i+1]里的“等于”上。当我写成>=，遇到1和1相等时，会继续往前扫，直到找到严格升序的位置。这样重复元素会被当成“降序区”的一部分，而不是拐点，逻辑就对了。

这是无数面试候选人会踩的坑。我第一次写的时候用的>，怎么跑怎么错，最后对着测试用例逐行推演才发现这个等号的问题。

5. 常见问题与排查技巧实录

5.1 边界条件导致的“翻转一切”

现象：输入[1,2]，输出变成了[2,1]，看起来对；输入[2,1]，输出[1,2]，也对；输入[1,1]，输出还是[1,1]，也对。但输入[1,2,1]，输出就错了，变成了[2,1,1]，而正确答案是[2,1,1]？等等，让我重新算一下。

用数字1、1、2组成排列，按字典序排：112, 121, 211。121的下一个确实是211。那[1,2,1]输出[2,1,1]是对的。如果哪里错了，通常是第一步找拐点时，误把nums[i] >= nums[i+1]写成>，导致i定位错误。

排查建议：拿到测试用例后，先手动写出该数组能组成的所有字典序排列，确认自己在第几位，再对照算法输出。这个手写列表的方法，比对着代码改半天高效得多。

5.2 死循环问题（如果你把代码嵌进循环调用）

有人会把“下一个排列”放在循环里，用来遍历所有排列。如果不小心，可能陷入死循环。

一个典型的错误写法：在函数内部对数组进行了复制，但返回值没有赋回去；或者调用完毕后数组没有变化。另一个可能：在while循环里反复调用下一个排列，但在数组已经是最大排列时，函数把它翻转为最小排列，于是又从最小开始走，形成无限循环。这不是算法错误，而是调用方忘掉了“循环终止条件”。

如果你确实要遍历所有排列，推荐这样写：

# 先排序，保证从最小排列开始 nums.sort() while True: print(nums) nextPermutation(nums) if nums == sorted(nums, reverse=True): break

这样就能在遍历完所有排列后退出。

5.3 反转区间写错导致答案诡异

反转操作reverse(nums.begin() + i + 1, nums.end())里，i+1是最容易写错的地方。

有人会写成reverse(nums.begin() + i, nums.end())，把拐点本身也反转进去了；有人会写成stack手动模拟反转，结果栈弹出顺序搞反；还有人用sort(nums.begin() + i + 1, nums.end())，虽然结果对，但复杂度变成了O(k log k)，在面试里会被人追问。

更隐蔽的一个错误是：如果第一步没找到拐点，i是-1，这时反转为reverse(nums.begin(), nums.end())是合法的，因为-1 + 1 = 0。这恰好就是要反转整个数组的情况。如果代码里对i做了特殊处理，反而容易出错。

5.4 常见问题速查表

5.5 测试用例设计指南

为了验证代码没问题，我建议至少准备以下几类测试用例：

• [1]：最小长度。
• [1,2]→[2,1]：最小非平凡情况。
• [2,1]→[1,2]：最大排列翻转到最小。
• [1,1,5]→[1,5,1]：重复元素。
• [5,4,3,2,1]→[1,2,3,4,5]：完全降序。
• [1,2,3,4,5]→[1,2,3,5,4]：最后两位交换。
• [1,3,2,2,2]→[2,1,2,2,3]：重复元素和拐点同时存在。

把这些用例全部跑通，你的实现基本就稳了。

6. 从“下一个排列”到更多扩展思考

6.1 如何改出“上一个排列”

理解了“下一个排列”，改出“上一个排列”就很简单，方向反过来就好：

1. 从右往左找第一个满足nums[i] > nums[i+1]的位置i。
2. 从右往左找第一个小于nums[i]的数nums[j]，交换。
3. 反转i+1到末尾。

结论可以直接背，但更重要的是理解背后的对称性：升序后缀对应“尽头”，降序后缀对应“起点”。一个方向是“最大中找最小”，另一个方向是“最小中找最大”。

6.2 与“第k个排列”的关系

LeetCode还有一道“第k个排列”，要求直接输出第k个排列，不依赖逐步调用。那道题可以用阶乘数系来做：每一位确定一个数字的区间，按k落在哪个区间决定取哪个数字。

但如果你不排斥效率低一些的写法，也能用“下一个排列”循环k-1次得到答案。对于时间要求不严格的场景，这种写法代码量少很多，作为面试兜底方案是可行的。当然，追求严谨时还是应该用阶乘数系的数学解法。

6.3 对环境与场景的联想

热词里出现了“origin图例横向排列”“窗口排列助手”，它们和本题共享“排列”这个概念，但实际场景完全不同。Origin里的图例横向排列是图表排版需求，窗口排列助手是操作系统窗口布局工具，而“下一个排列”是纯算法问题。

不过它们确实共享一个底层直觉：顺序是有结构的，不是随机的。图例怎么排更好看、窗口怎么排更高效，本质都是在某种策略下找到“更好的顺序”。算法题里的“下一个排列”只是把“更好”定义成了字典序中的下一个，而工程师在实际工程里，经常要定义自己的“更好”标准——可以是面积利用率、可读性、路径最短。理解这一点，比背下这一道题的解法更有价值。

6.4 标准库里的同款实现

C++ 的std::next_permutation实现细节和上面几乎一致，但它返回一个bool，表示是否还存在下一个排列。如果返回false，说明已经遍历完所有排列，此时容器被重置为升序状态。

如果你在实现自己的工具库，建议模仿这个接口设计：返回 bool 而不是直接修改完就结束。这样调用方就能自然地写在while循环里，不用担心死循环问题。

下面是一个可以借鉴的实现骨架：

template<typename Iterator> bool nextPermutation(Iterator first, Iterator last) { if (first == last) return false; Iterator i = last; if (first == --i) return false; while (true) { Iterator i1 = i; if (*--i < *i1) { Iterator i2 = last; while (!(*i < *--i2)) {} std::iter_swap(i, i2); std::reverse(i1, last); return true; } if (i == first) { std::reverse(first, last); return false; } } }

这套实现比较紧凑，迭代器操作稍多，但逻辑和前面说的完全一致。值得花点时间逐行读一遍，能加深对迭代器边界和算法步骤的理解。

6.5 关于递归全排列的对比

很多人学全排列时先接触的是递归交换法：

def permute(nums): res = [] def dfs(path, used): if len(path) == len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue used[i] = True path.append(nums[i]) dfs(path, used) path.pop() used[i] = False dfs([], [False] * len(nums)) return res

递归法适合“生成全部排列”，时间复杂度和空间复杂度都是O(n!)和O(n)。“下一个排列”则适合“只走到下一个状态”，时间和空间都压缩到极低。两者不是互相替代的关系，而是不同场景下的工具。

如果你需要在递归回溯时随时判断“这个排列的下一个状态”，可以用“下一个排列”的思想做剪枝；如果你需要完整枚举，递归法更直观。

7. 个人实操经验与踩坑总结

最后分享几条我在实际写代码过程中总结出来的经验。

第一，遇到字典序排列问题，先画状态链。把几个连续排列写在纸上，观察哪一段变了、哪一段没变，规律会自己浮出来。我最初啃这道题时就是靠手写123 → 132 → 213 → 231 → 312 → 321这条链看懂的。

第二，两个“等于”是重灾区。第一步的>=和第二步的<=，少一个等号就会出现错误答案。建议在写完代码后，专门构造一个带重复元素的用例去验这两行。

第三，反转比排序好。虽然反转的写法看起来有点绕，但它在任何时候都成立——因为交换后后缀必然是降序的。这个性质是算法设计的一部分，不是巧合。理解了它，你写代码时就不会想着“保险起见用sort()”，而是会自信地写reverse()。

第四，这道题适合背诵模板，但不能只背。面试官很可能在你看似轻松地写完代码后追问一句“为什么从右往左”，答不上来印象分会大打折扣。我的建议是至少能手推一遍[1,3,5,4,2]这样的用例，把每一步的理由说清楚。

假如你是第一次接触这道题，不用急着追求一遍写对。先用暴力法生成全排列对照着看，哪怕生成到n=4就已经能验证算法的正确性了。多跑几个用例，多推演几遍，这道题会成为你脑子里非常踏实的一块基石。