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 暴力法为什么会炸面对“下一个排列”这个问题最直觉的思路是这样的生成这个数组能组成的全部排列按字典序排序找到当前排列的位置取它的下一个。这个思路正确吗正确。可行吗不可行。原因很简单n个不同数字的全排列共有n!个。n10时是三百多万n12时已经接近五亿。而题目里数组长度上限是100100!是个大到没有任何计算机能枚举完的数字。你连枚举都枚举不完更谈不上排序和查找了。所以这道题真正想考察的不是“你会不会全排列”而是“你懂不懂字典序排列的结构规律”。排列之间不是散乱分布的它们之间有一条隐藏的序关系找到这个序关系就能直接算出来而不是“生成所有再找”。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 关键观察从右往左找第一个“上升点”基于上面的规律可以得到一个非常优雅的算法流程从右往左遍历数组找到第一个满足a[i] a[i1]的位置i。这个位置就是“拐点”。如果找不到这样的i说明整个数组是降序的也就是最大排列直接反转整个数组得到最小排列。如果找到了i再次从右往左找到第一个大于a[i]的数字a[j]。交换a[i]和a[j]。把i1到末尾这一段反转让它变成升序也就是最小排列。为什么第一步一定要从右往左找因为我们要找的是“尽可能靠右的拐点”。只有拐点越靠右改动的前缀越短得到的排列才越是“下一个”——它保证增幅最小。为什么第二步找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]13 1不满足再往前a[6]5和a[7]35 3不满足a[5]6和a[6]56 5不满足a[4]7和a[5]67 6不满足a[3]4和a[4]74 7满足。所以i 3a[3] 4。此时从i1到末尾的部分[7,6,5,3,1]是一个严格降序序列。为什么这个降序序列很重要因为它意味着“以[1,5,8,4]为前缀的排列已经穷尽了所有可能”。任何对这个前缀的微调比如把某一位变大都会产生更大的排列但我们现在要的是“最小增幅”所以要尽量保持前缀不动或者只动最后一位可能的位置。第二步从右往左找第一个大于a[i]的数。从数组末尾开始扫a[8]1不大于4a[7]3不大于4a[6]5大于4找到了。所以j 6a[j] 5。这里注意因为i1之后是降序的从右往左扫其实就是从“最小的元素”往“最大的元素”扫第一个大于a[i]的数一定是所有大于a[i]的数里最小的那个。这保证了交换后前缀的增幅是最小的。第三步交换a[i]和a[j]。交换后数组变成[1,5,8,5,7,6,4,3,1]。这里有个小细节交换后i1到末尾这一段[7,6,4,3,1]仍然是降序的。为什么因为a[j]是从右往左第一个大于a[i]的数它右边的数全部小于等于a[i]所以把a[i]这个较小的值换到j的位置后它不会打破右侧的降序性质——右侧本来就是降序且这些数现在都更小了降序依然成立。第四步反转i1到末尾。把[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[i1]于是直接反转整个数组反转后还是[1]。情况二数组已经是降序最大排列。比如[3,2,1]。从右往左找不到任何a[i] a[i1]直接反转整个数组得到[1,2,3]。这正好对应题目里说的“如果不存在下一个更大的排列则重新排列成最小的排列”。情况三所有元素都相同。比如[2,2,2]。从右往左找2 2不成立所以直接反转结果还是[2,2,2]。这其实是降序情况的一种特殊形态。情况四数组本身已经升序。比如[1,2,3,4]。从右往左找第一个满足条件的是i2因为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[i1]: 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[i1:]注意两个细节第一步的循环条件是nums[i] nums[i1]不是。必须把等于的情况也跳过否则遇到重复元素时会把相等元素误判成拐点。第二步的循环条件是nums[j] nums[i]同样要跳过等于的情况。我们要找的是严格大于nums[i]的数。4.2 C 实现class Solution { public: void nextPermutation(vectorint 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]); } // 反转 i1 到末尾 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] # 反转 i1 到末尾 left, right i 1, len(nums) - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 14.4 一个完整的手动模拟用例用[1,5,1]来模拟一遍完整流程从右往左找比较5和15 1不满足比较1和51 5满足所以i 0。从右往左找第一个大于nums[0]1的数末尾是1等于1不算再看55大于1所以j 1。交换nums[0]和nums[1]得到[5,1,1]。反转i11到末尾[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[i1]里的“等于”上。当我写成遇到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[i1]写成导致i定位错误。排查建议拿到测试用例后先手动写出该数组能组成的所有字典序排列确认自己在第几位再对照算法输出。这个手写列表的方法比对着代码改半天高效得多。5.2 死循环问题如果你把代码嵌进循环调用有人会把“下一个排列”放在循环里用来遍历所有排列。如果不小心可能陷入死循环。一个典型的错误写法在函数内部对数组进行了复制但返回值没有赋回去或者调用完毕后数组没有变化。另一个可能在while循环里反复调用下一个排列但在数组已经是最大排列时函数把它翻转为最小排列于是又从最小开始走形成无限循环。这不是算法错误而是调用方忘掉了“循环终止条件”。如果你确实要遍历所有排列推荐这样写# 先排序保证从最小排列开始 nums.sort() while True: print(nums) nextPermutation(nums) if nums sorted(nums, reverseTrue): break这样就能在遍历完所有排列后退出。5.3 反转区间写错导致答案诡异反转操作reverse(nums.begin() i 1, nums.end())里i1是最容易写错的地方。有人会写成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 常见问题速查表症状可能原因解决方法输入[1,1,5]输出[5,1,1]第一步循环用了而非改成nums[i] nums[i1]输出结果比正确答案大很多第二步找j时没让相等元素跳过改成nums[j] nums[i]数组没有变化忘记原地修改或者复制数组操作有误确认直接操作传入的数组引用越界异常第二步循环从n-1开始但条件里j 0被漏掉检查边界条件j不可能为负但代码要能应对i-1结果整体是降序反转区间写错确认是i1到末尾不是i到末尾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 如何改出“上一个排列”理解了“下一个排列”改出“上一个排列”就很简单方向反过来就好从右往左找第一个满足nums[i] nums[i1]的位置i。从右往左找第一个小于nums[i]的数nums[j]交换。反转i1到末尾。结论可以直接背但更重要的是理解背后的对称性升序后缀对应“尽头”降序后缀对应“起点”。一个方向是“最大中找最小”另一个方向是“最小中找最大”。6.2 与“第k个排列”的关系LeetCode还有一道“第k个排列”要求直接输出第k个排列不依赖逐步调用。那道题可以用阶乘数系来做每一位确定一个数字的区间按k落在哪个区间决定取哪个数字。但如果你不排斥效率低一些的写法也能用“下一个排列”循环k-1次得到答案。对于时间要求不严格的场景这种写法代码量少很多作为面试兜底方案是可行的。当然追求严谨时还是应该用阶乘数系的数学解法。6.3 对环境与场景的联想热词里出现了“origin图例横向排列”“窗口排列助手”它们和本题共享“排列”这个概念但实际场景完全不同。Origin里的图例横向排列是图表排版需求窗口排列助手是操作系统窗口布局工具而“下一个排列”是纯算法问题。不过它们确实共享一个底层直觉顺序是有结构的不是随机的。图例怎么排更好看、窗口怎么排更高效本质都是在某种策略下找到“更好的顺序”。算法题里的“下一个排列”只是把“更好”定义成了字典序中的下一个而工程师在实际工程里经常要定义自己的“更好”标准——可以是面积利用率、可读性、路径最短。理解这一点比背下这一道题的解法更有价值。6.4 标准库里的同款实现C 的std::next_permutation实现细节和上面几乎一致但它返回一个bool表示是否还存在下一个排列。如果返回false说明已经遍历完所有排列此时容器被重置为升序状态。如果你在实现自己的工具库建议模仿这个接口设计返回 bool 而不是直接修改完就结束。这样调用方就能自然地写在while循环里不用担心死循环问题。下面是一个可以借鉴的实现骨架templatetypename 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]这样的用例把每一步的理由说清楚。假如你是第一次接触这道题不用急着追求一遍写对。先用暴力法生成全排列对照着看哪怕生成到n4就已经能验证算法的正确性了。多跑几个用例多推演几遍这道题会成为你脑子里非常踏实的一块基石。