刷题这事我一直有个观点真正值得反复琢磨的往往不是那些难到劝退的压轴题而是看起来“中等偏易”、背后却藏着完整套路模板的题。力扣第31题“下一个排列”就是其中最典型的一道它同时出现在热题100和不少大厂笔试题单里可每次面试问到能一次写对的人真不多。这道题讲的是什么一句话给定一个整数数组把它重排成字典序意义上的下一个更大的排列如果已经是最大排列就重排成最小的升序排列。难点不在于思路多玄而在于你能否从“全排列”的直觉里跳出来抓住“找降序边界”这个核心规律再用双指针原地完成交换和反转。这篇文章我想把这道题从头到尾拆开讲清楚先建立直觉和规律再对比暴力和线性解法然后给出带注释的可运行代码最后把我在刷题和面试中踩过的坑、被追问过的变体一起整理出来。不管你是刚开始刷力扣的新手还是准备冲刺热题100的进阶选手这篇笔记应该都能帮你把这道题彻底吃透。1. 题目理解与思路拆解1.1 先看看题目到底在说什么原题描述里有一句话很关键整数数组的“下一个排列”是指其整数的下一个字典序更大的排列。更正式地说给定数组nums需要原地修改它将它重排成按字典序排列时下一个比当前排列更大的排列如果不存在下一个更大的排列就将数字重新排列成最小的排列即升序排列。这里有个硬性约束必须原地修改只允许使用额外常数空间。也就是说你不能新建一个数组来存放结果也不能用递归生成所有排列再去找下一个空间复杂度必须控制在 O(1)。光看文字可能有点抽象直接看例子最直观[1, 2, 3]的下一个排列是[1, 3, 2][3, 2, 1]已经没有更大的排列了所以重排成[1, 2, 3][1, 1, 5]的下一个排列是[1, 5, 1]这三个例子覆盖了三种典型情况普通递增尾、完全降序的最大排列、包含重复元素的排列。把这三个例子弄明白题目就理解了一半。什么叫“字典序”类比一下英文词典里单词的排序方式先比较第一个字母第一个字母相同再比较第二个以此类推。数字排列也是一个道理从头到尾逐位比较找到第一个不相等的位置小的那位所在排列就排在前面。比如[1, 3, 2]和[2, 1, 3]第一位 1 小于 2所以[1, 3, 2]排在[2, 1, 3]前面。题目要我们做的本质上就是在所有排列构成的字典序序列里找到当前排列紧挨着的下一项。1.2 核心难点为什么不能直接“找下一个更大的数”很多人第一次拿到这题脑子里蹦出来的想法是把数组当成一个数字然后找比它大的最小数字组合。比如[1, 2, 3]下一个就是[1, 3, 2]这看起来像是把末尾两个数交换了一下。但换一组数据就露馅了[1, 5, 8, 4, 7, 6, 5, 3, 1]的下一个排列是多少直觉很难一下给出答案。问题出在排列的“下一个更大”不是简单的局部交换而是需要满足两个条件变大的幅度要尽可能小也就是“下一个”而不是“跳过好几个”。新排列必须大于原排列也就是说变化发生的位置越靠右越好因为左边的高位决定大小越靠右的调整对数值影响越小。顺着这个思路真正要解决的问题就是找到最靠右的、还能“变大”的位置在那一位放一个比当前值更大但尽可能小的数然后把后面的部分重排成最小的顺序。这是整道题最核心的直觉后面所有的算法步骤都围绕它展开。1.3 关键规律从右往左找到第一个“降序对”那怎么找到“最靠右还能变大的位置”呢答案是从右往左扫描找到第一个满足nums[i] nums[i 1]的位置 i。为什么是从右往左找举个例子看后缀[... , 7, 6, 5, 3, 1]这个后缀从右往左看一直是严格递增的也就是从左往右看是严格递减的也就是说无论你怎么交换这些元素都只能得到一个更小的排列无法让整个数组变大。所以我们要找的是“破坏”这个降序结构的第一个位置。拿[1, 5, 8, 4, 7, 6, 5, 3, 1]来说从右往左看1 和 3 相比1 3继续3 和 5 相比3 5继续5 和 6 相比5 6继续6 和 7 相比6 7继续7 和 4 相比4 7不7 大于 4这里出现了第一个“反例”所以 i 指向 4下标 3。这个位置意味着以4开头的整个后缀[4, 7, 6, 5, 3, 1]已经是这些数字能组成的最大排列了想要得到下一个更大的排列必须把4换成一个更大的数字。找到这个 i 之后算法就完成了第一步也是最难理解的一步。后面要做的是把“变大”这件事控制在最小幅度内。2. 从暴力到最优两种解法的对比2.1 暴力解法生成全排列再找下一个可行吗在讲标准解法之前先聊聊很多人第一反应想到的暴力方案把数组的所有排列全部生成出来按字典序排序找到当前排列的位置然后输出下一个。理论上这完全可行代码写起来也不难先用回溯或递归生成全排列再排序再线性查找。但问题出在复杂度上一个有 n 个元素的数组全排列数量是 n!。n 10 的时候是 3628800 个n 12 的时候接近 4.8 亿个时间和空间都直接爆炸。题目限定数组长度最大为 100n! 是完全不可行的量级。所以这道题的本质就是在提醒你不要枚举要找规律。实际上很多“排列类”问题的最优解都不是靠搜索硬扛而是靠分析排列结构本身。暴力的价值在于验证答案。我刷题的时候经常用暴力解法当测试对照写一个生成全排列的辅助函数用nextPermutation的结果和它对比确认小规模数据上的正确性。这个技巧在本地调试时非常好用但提交到力扣上还是得用线性解法。2.2 线性解法的推导三步走的由来标准解法是业界公认的“下一个排列算法”也是 C 标准库std::next_permutation的实现原理。整段算法的推导过程可以清晰地拆成三步每一步都有明确的“为什么”第一步从右往左找到第一个nums[i] nums[i 1]的位置 i。这一步的意义是定位“最低可调整位”。i 右侧的所有元素构成一个降序序列这意味着右侧子序列已经是这些元素能排成的最大排列。没有 i 这个位置整个序列已经处于字典序末尾。第二步在 i 右侧找到大于nums[i]的最小元素记为nums[j]。为什么要找“最小的大于”因为我们要让新排列比原排列大但又不能大太多。右侧序列是降序的所以从右往左扫一遍第一个大于nums[i]的元素就是右侧最小的大于nums[i]的元素。第三步交换nums[i]和nums[j]然后把 i 右侧的子序列反转。交换后i 位置已经比原来大了右侧剩余元素只要排成最小顺序升序就能保证整个排列是“紧挨着的下一个”。由于右侧原本是降序交换之后仍然是降序所以直接反转就能得到升序。这三步环环相扣第一步找边界第二步做最小增量第三步重排后缀。缺失任何一步都可能得到一个错误或者跳步的答案。3. 代码实现与关键细节3.1 JavaScript 版完整实现力扣上用 JavaScript 刷题的人很多直接给出一版通过验证的代码每一行都拆开讲/** * param {number[]} nums * return {void} Do not return anything, modify nums in-place instead. */ var nextPermutation function(nums) { const n nums.length; // 第一步从右往左找第一个升序对 (nums[i] nums[i1]) let i n - 2; while (i 0 nums[i] nums[i 1]) { i--; } // 第二步如果找到了升序对在右侧找大于 nums[i] 的最小元素 if (i 0) { let j n - 1; while (j 0 nums[j] nums[i]) { j--; } // 交换 [nums[i], nums[j]] [nums[j], nums[i]]; } // 第三步反转 i1 到末尾的部分 let left i 1; let right n - 1; while (left right) { [nums[left], nums[right]] [nums[right], nums[left]]; left; right--; } return nums; };这段代码有几个细节值得特别留意。第一第一步用的是while (i 0 nums[i] nums[i 1])注意这里的而不是。为什么因为题目允许重复元素。如果是遇到[1, 1]这种相等情况i 会停在索引 0可实际上[1, 1]已经不存在更大的排列了应该整体反转。用才能把相等的情况也归入“降序”避免错误地尝试交换。第二第二步找 j 的时候条件同样是而不是。在右侧降序区间里我们要的是“严格大于 nums[i] 的最小值”必须跳过所有等于 nums[i] 的元素否则交换后可能得到不增反减的排列。比如[1, 5, 1]如果找 j 时用了会选中值为 1 的元素交换后变成[1, 1, 5]反而变小了。第三第三步反转的起始位置是i 1。如果整个数组已经是完全降序比如[3, 2, 1]循环结束后 i 会变成 -1此时反转整个数组正好得到升序的[1, 2, 3]。这个边界情况的处理是整个算法优雅的地方之一不需要单独判断“是否存在下一个排列”直接靠反转兜底。3.2 手把手走一遍完整示例光看代码不如实际走一遍。还是用[1, 5, 8, 4, 7, 6, 5, 3, 1]来演算数组长度 n 9i 从 7 开始。nums[7]3和nums[8]13 1i 左移到 6。nums[6]5和nums[7]35 3i 左移到 5。nums[5]6和nums[6]56 5i 左移到 4。nums[4]7和nums[5]67 6i 左移到 3。nums[3]4和nums[4]74 7循环停止i 3。此时找到第一个可调整位值 4。接着在右侧[7, 6, 5, 3, 1]里从右往左找第一个大于 4 的数1 不大于 43 不大于 45 大于 4所以 j 6值是 5。交换nums[3]和nums[6]数组变成[1, 5, 8, 5, 7, 6, 4, 3, 1]。最后反转下标 4 到 8 的部分[7, 6, 4, 3, 1]反转后是[1, 3, 4, 6, 7]整个数组变为[1, 5, 8, 5, 1, 3, 4, 6, 7]。这个结果是不是真正的“下一个排列”可以验证一下原排列以[1, 5, 8, 4]开头所有以[1, 5, 8, 4]开头、后面跟[7, 6, 5, 3, 1]的排列中[1, 5, 8, 4, 7, 6, 5, 3, 1]已经是最大的因为后缀是降序。所以下一个排列必须把第 4 位从 4 换成 5右侧最小的大于 4 的元素然后后缀排成最小顺序也就是升序。结果和我们演算的一致。3.3 Python 版本与语言差异除了 JavaScriptPython 版本在面试手写时也经常被要求给出。核心逻辑完全一样只是语法略有差异class Solution: def nextPermutation(self, nums: list[int]) - None: Do not return anything, modify nums in-place instead. n len(nums) i n - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: j n - 1 while j 0 and nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] left, right i 1, n - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1Python 里交换两个元素可以直接用nums[i], nums[j] nums[j], nums[i]不用借助临时变量。此外力扣的函数签名里nums是list[int]不需要返回值因为它要求原地修改。这一点和 JavaScript 版的return nums不同别看是小区别面试时被问“为什么不需要 return”也常常是考察点。时间复杂度方面三步操作都是单次线性扫描整体是 O(n)。空间上只用了常数个临时变量满足题目的 O(1) 要求。这也是这道题最让人舒服的地方思路一旦打通代码非常短性能还极其优秀。4. 面试场景与高频考点4.1 面试官可能会问的追问这道题在面试中出现的频率非常高而且面试官往往不会满足于你写出代码还会顺着往下追问。我整理了几个高频追问方向你可以提前准备。第一个常问的是“你能解释一下为什么交换后直接反转就能得到升序吗”这个问题考察的是对算法本质的理解。原因在于i 右侧原本是一个降序序列我们找 j 的时候是从右往左找第一个大于 nums[i] 的元素它实际上是右侧序列中从右往左数第一个“比 nums[i] 大”的数。交换 nums[i] 和 nums[j] 之后nums[j] 原来的位置被一个比它小的数占据而右侧其他元素的大小关系没有变整个右侧仍然保持降序。所以反转后得到的就是升序也就是最小的后缀排列。第二个常问的是“如果数组中存在大量重复元素这个算法还成立吗”答案是成立。关键在于比较条件里用了和把相等的情况当作“不可用”处理保证找到的永远是最靠右的可调整位以及右侧严格大于目标值的最小元素。第三个问题是开放性的“你能计算出任意排列在全排列中的排名吗”这涉及到康托展开是一个更深入的数学话题。虽然力扣第 31 题本身不要求这个但如果面试官想考察你的延展能力可能会从这里切入。我的建议是先把 nextPermutation 本身讲透再提一句“连续调用 n 次可以得到第 n 个后续排列也可以反过来设计 prevPermutation”这样展示出的思维深度会明显不一样。4.2 相关题目与变体迁移刷题最忌讳的是“一题一题孤立地刷”。这道题虽然短小但它像一条线索串联起好几道经典题目把它们放在一起看效率会高很多。先说最直接相关的力扣 46 题“全排列”和 47 题“全排列 II”。46 题要求输出所有排列47 题是含重复元素的版本。如果理解了 nextPermutation完全可以用它来生成全排列先排序得到最小排列然后不断调用 nextPermutation直到回到最小排列为止。相比回溯法这种方式写起来更简洁思路也更接近“字典序生成”的语义。还有一道很有意思的变体力扣 556 题“下一个更大元素 III”。它本质上就是第 31 题的“数字版”给定一个正整数 n找出由相同数字组成的、大于 n 的最小整数。做法就是把 n 转成数组跑一遍 nextPermutation再把数组转回数字检查是否越界。这道题我在面试中见过好几次它考察的其实是同一套能力能否把陌生问题抽象成已经做过的经典题。更进一步可以思考如何写出“上一个排列”prevPermutation。实现方式完全对称从右往左找第一个降序对nums[i] nums[i 1]在右侧找小于nums[i]的最大元素交换再把右侧反转。写一遍 prevPermutation你对字典序排列的理解会再深一层。4.3 刷题策略如何把一道题刷出十道题的效果很多人在热题 100 上刷题往往追求“数量”今天刷 5 道、明天刷 8 道但过两周回头一看全忘了。这是非常普遍的误区。我个人更推荐“围绕核心题做刻意练习”每做完一道有价值的题就主动去找它的变体、追问和相似题。以第 31 题为例一个完整的学习闭环应该包含四层第一层能独立写出 nextPermutation 并解释原理。第二层能快速套用到 556 题这类数字版题目上。第三层能说出它与全排列生成的联系并手动推导几个排列的字典序顺序。第四层能扩展到 prevPermutation 以及排列排名康托展开。做到第三层和第四层这道题在你脑子里就不再是一个孤立的代码片段而是一张可以随时调用的知识网络。面试时哪怕面试官换一个包装你也能一眼看出内核。5. 常见错误与排查技巧实录5.1 高频错误速查表这道题代码不长但新手容易出错的地方反而很集中。我把常见错误整理成一张速查表方便你写完代码后逐项对照检查。错误类型错误写法正确写法后果第一步比较符错误nums[i] nums[i 1]nums[i] nums[i 1]重复元素场景下无法找到正确的可调整位可能输出错误结果第二步比较符错误nums[j] nums[i]nums[j] nums[i]可能选中等于 nums[i] 的元素交换后排列不增反减忘记反转交换后直接返回必须反转 i1 之后的子数组后缀仍然降序导致得到的不是字典序意义上的“下一个”反转区间错误left ileft i 1把已经调整好的 nums[i] 也反转了结果完全错乱i 初始值错误let i n - 1let i n - 2需要比较 nums[i] 和 nums[i1]所以 i 最右只能到 n-2这份速查表里的几类错误我在实际调试中都踩过。最隐蔽的是第一个因为测试用例如果全是无重复元素和结果一模一样只有遇到[1, 1]这种用例才会暴露。5.2 实测排查方法小数据穷举验证如果写完代码不确定是否正确有一个非常实用的小技巧写一个暴力生成全排列的函数和小数据规模下跑 nextPermutation 的结果做对比。具体做法是对于长度为 1 到 6 的数组穷举所有排列并排序然后依次调用 nextPermutation检查每次返回的结果是否和排序后列表中的下一项一致。只要小规模全部通过算法在逻辑上基本就是正确的。这个验证方式能帮你快速定位是思路问题还是实现问题尤其是在处理重复元素的时候暴力对照法几乎是最好的调试工具。我自己刷这道题时就是先用暴力方法验证了[1, 1, 5]这些容易出错的重复元素用例才发现比较符的问题。如果你也在调试建议不要只盯着力扣自带的那几个示例手动构造一些边界用例完全升序、完全降序、全相同元素、最大长度数组覆盖住所有分支。5.3 我的个人心得最后分享一点体会。这道题最奇妙的地方在于它把“字典序”这个偏数学的概念变成了一个特别具象的工程问题找降序边界、找交换对象、反转后缀。每一步单独看都特别简单但组合在一起就是一套完整的算法。这让我想起写代码时的一个规律——真正优雅的解法往往不是因为用了什么高深的数据结构而是因为看问题的角度对了把复杂的全局问题简化成了几个局部的操作。我经常和刷题的朋友说第 31 题“下一个排列”是值得背下来的少数题目之一不是因为它答案短而是因为它代表了“字典序排列”这一类问题的标准范式。吃透它再去碰全排列生成、排列序列、下一个更大元素这些题你会发现自己几乎不用重新学都是在做同一件事的排列组合。
刷题这事我一直有个观点真正值得反复琢磨的往往不是那些难到劝退的压轴题而是看起来“中等偏易”、背后却藏着完整套路模板的题。力扣第31题“下一个排列”就是其中最典型的一道它同时出现在热题100和不少大厂笔试题单里可每次面试问到能一次写对的人真不多。这道题讲的是什么一句话给定一个整数数组把它重排成字典序意义上的下一个更大的排列如果已经是最大排列就重排成最小的升序排列。难点不在于思路多玄而在于你能否从“全排列”的直觉里跳出来抓住“找降序边界”这个核心规律再用双指针原地完成交换和反转。这篇文章我想把这道题从头到尾拆开讲清楚先建立直觉和规律再对比暴力和线性解法然后给出带注释的可运行代码最后把我在刷题和面试中踩过的坑、被追问过的变体一起整理出来。不管你是刚开始刷力扣的新手还是准备冲刺热题100的进阶选手这篇笔记应该都能帮你把这道题彻底吃透。1. 题目理解与思路拆解1.1 先看看题目到底在说什么原题描述里有一句话很关键整数数组的“下一个排列”是指其整数的下一个字典序更大的排列。更正式地说给定数组nums需要原地修改它将它重排成按字典序排列时下一个比当前排列更大的排列如果不存在下一个更大的排列就将数字重新排列成最小的排列即升序排列。这里有个硬性约束必须原地修改只允许使用额外常数空间。也就是说你不能新建一个数组来存放结果也不能用递归生成所有排列再去找下一个空间复杂度必须控制在 O(1)。光看文字可能有点抽象直接看例子最直观[1, 2, 3]的下一个排列是[1, 3, 2][3, 2, 1]已经没有更大的排列了所以重排成[1, 2, 3][1, 1, 5]的下一个排列是[1, 5, 1]这三个例子覆盖了三种典型情况普通递增尾、完全降序的最大排列、包含重复元素的排列。把这三个例子弄明白题目就理解了一半。什么叫“字典序”类比一下英文词典里单词的排序方式先比较第一个字母第一个字母相同再比较第二个以此类推。数字排列也是一个道理从头到尾逐位比较找到第一个不相等的位置小的那位所在排列就排在前面。比如[1, 3, 2]和[2, 1, 3]第一位 1 小于 2所以[1, 3, 2]排在[2, 1, 3]前面。题目要我们做的本质上就是在所有排列构成的字典序序列里找到当前排列紧挨着的下一项。1.2 核心难点为什么不能直接“找下一个更大的数”很多人第一次拿到这题脑子里蹦出来的想法是把数组当成一个数字然后找比它大的最小数字组合。比如[1, 2, 3]下一个就是[1, 3, 2]这看起来像是把末尾两个数交换了一下。但换一组数据就露馅了[1, 5, 8, 4, 7, 6, 5, 3, 1]的下一个排列是多少直觉很难一下给出答案。问题出在排列的“下一个更大”不是简单的局部交换而是需要满足两个条件变大的幅度要尽可能小也就是“下一个”而不是“跳过好几个”。新排列必须大于原排列也就是说变化发生的位置越靠右越好因为左边的高位决定大小越靠右的调整对数值影响越小。顺着这个思路真正要解决的问题就是找到最靠右的、还能“变大”的位置在那一位放一个比当前值更大但尽可能小的数然后把后面的部分重排成最小的顺序。这是整道题最核心的直觉后面所有的算法步骤都围绕它展开。1.3 关键规律从右往左找到第一个“降序对”那怎么找到“最靠右还能变大的位置”呢答案是从右往左扫描找到第一个满足nums[i] nums[i 1]的位置 i。为什么是从右往左找举个例子看后缀[... , 7, 6, 5, 3, 1]这个后缀从右往左看一直是严格递增的也就是从左往右看是严格递减的也就是说无论你怎么交换这些元素都只能得到一个更小的排列无法让整个数组变大。所以我们要找的是“破坏”这个降序结构的第一个位置。拿[1, 5, 8, 4, 7, 6, 5, 3, 1]来说从右往左看1 和 3 相比1 3继续3 和 5 相比3 5继续5 和 6 相比5 6继续6 和 7 相比6 7继续7 和 4 相比4 7不7 大于 4这里出现了第一个“反例”所以 i 指向 4下标 3。这个位置意味着以4开头的整个后缀[4, 7, 6, 5, 3, 1]已经是这些数字能组成的最大排列了想要得到下一个更大的排列必须把4换成一个更大的数字。找到这个 i 之后算法就完成了第一步也是最难理解的一步。后面要做的是把“变大”这件事控制在最小幅度内。2. 从暴力到最优两种解法的对比2.1 暴力解法生成全排列再找下一个可行吗在讲标准解法之前先聊聊很多人第一反应想到的暴力方案把数组的所有排列全部生成出来按字典序排序找到当前排列的位置然后输出下一个。理论上这完全可行代码写起来也不难先用回溯或递归生成全排列再排序再线性查找。但问题出在复杂度上一个有 n 个元素的数组全排列数量是 n!。n 10 的时候是 3628800 个n 12 的时候接近 4.8 亿个时间和空间都直接爆炸。题目限定数组长度最大为 100n! 是完全不可行的量级。所以这道题的本质就是在提醒你不要枚举要找规律。实际上很多“排列类”问题的最优解都不是靠搜索硬扛而是靠分析排列结构本身。暴力的价值在于验证答案。我刷题的时候经常用暴力解法当测试对照写一个生成全排列的辅助函数用nextPermutation的结果和它对比确认小规模数据上的正确性。这个技巧在本地调试时非常好用但提交到力扣上还是得用线性解法。2.2 线性解法的推导三步走的由来标准解法是业界公认的“下一个排列算法”也是 C 标准库std::next_permutation的实现原理。整段算法的推导过程可以清晰地拆成三步每一步都有明确的“为什么”第一步从右往左找到第一个nums[i] nums[i 1]的位置 i。这一步的意义是定位“最低可调整位”。i 右侧的所有元素构成一个降序序列这意味着右侧子序列已经是这些元素能排成的最大排列。没有 i 这个位置整个序列已经处于字典序末尾。第二步在 i 右侧找到大于nums[i]的最小元素记为nums[j]。为什么要找“最小的大于”因为我们要让新排列比原排列大但又不能大太多。右侧序列是降序的所以从右往左扫一遍第一个大于nums[i]的元素就是右侧最小的大于nums[i]的元素。第三步交换nums[i]和nums[j]然后把 i 右侧的子序列反转。交换后i 位置已经比原来大了右侧剩余元素只要排成最小顺序升序就能保证整个排列是“紧挨着的下一个”。由于右侧原本是降序交换之后仍然是降序所以直接反转就能得到升序。这三步环环相扣第一步找边界第二步做最小增量第三步重排后缀。缺失任何一步都可能得到一个错误或者跳步的答案。3. 代码实现与关键细节3.1 JavaScript 版完整实现力扣上用 JavaScript 刷题的人很多直接给出一版通过验证的代码每一行都拆开讲/** * param {number[]} nums * return {void} Do not return anything, modify nums in-place instead. */ var nextPermutation function(nums) { const n nums.length; // 第一步从右往左找第一个升序对 (nums[i] nums[i1]) let i n - 2; while (i 0 nums[i] nums[i 1]) { i--; } // 第二步如果找到了升序对在右侧找大于 nums[i] 的最小元素 if (i 0) { let j n - 1; while (j 0 nums[j] nums[i]) { j--; } // 交换 [nums[i], nums[j]] [nums[j], nums[i]]; } // 第三步反转 i1 到末尾的部分 let left i 1; let right n - 1; while (left right) { [nums[left], nums[right]] [nums[right], nums[left]]; left; right--; } return nums; };这段代码有几个细节值得特别留意。第一第一步用的是while (i 0 nums[i] nums[i 1])注意这里的而不是。为什么因为题目允许重复元素。如果是遇到[1, 1]这种相等情况i 会停在索引 0可实际上[1, 1]已经不存在更大的排列了应该整体反转。用才能把相等的情况也归入“降序”避免错误地尝试交换。第二第二步找 j 的时候条件同样是而不是。在右侧降序区间里我们要的是“严格大于 nums[i] 的最小值”必须跳过所有等于 nums[i] 的元素否则交换后可能得到不增反减的排列。比如[1, 5, 1]如果找 j 时用了会选中值为 1 的元素交换后变成[1, 1, 5]反而变小了。第三第三步反转的起始位置是i 1。如果整个数组已经是完全降序比如[3, 2, 1]循环结束后 i 会变成 -1此时反转整个数组正好得到升序的[1, 2, 3]。这个边界情况的处理是整个算法优雅的地方之一不需要单独判断“是否存在下一个排列”直接靠反转兜底。3.2 手把手走一遍完整示例光看代码不如实际走一遍。还是用[1, 5, 8, 4, 7, 6, 5, 3, 1]来演算数组长度 n 9i 从 7 开始。nums[7]3和nums[8]13 1i 左移到 6。nums[6]5和nums[7]35 3i 左移到 5。nums[5]6和nums[6]56 5i 左移到 4。nums[4]7和nums[5]67 6i 左移到 3。nums[3]4和nums[4]74 7循环停止i 3。此时找到第一个可调整位值 4。接着在右侧[7, 6, 5, 3, 1]里从右往左找第一个大于 4 的数1 不大于 43 不大于 45 大于 4所以 j 6值是 5。交换nums[3]和nums[6]数组变成[1, 5, 8, 5, 7, 6, 4, 3, 1]。最后反转下标 4 到 8 的部分[7, 6, 4, 3, 1]反转后是[1, 3, 4, 6, 7]整个数组变为[1, 5, 8, 5, 1, 3, 4, 6, 7]。这个结果是不是真正的“下一个排列”可以验证一下原排列以[1, 5, 8, 4]开头所有以[1, 5, 8, 4]开头、后面跟[7, 6, 5, 3, 1]的排列中[1, 5, 8, 4, 7, 6, 5, 3, 1]已经是最大的因为后缀是降序。所以下一个排列必须把第 4 位从 4 换成 5右侧最小的大于 4 的元素然后后缀排成最小顺序也就是升序。结果和我们演算的一致。3.3 Python 版本与语言差异除了 JavaScriptPython 版本在面试手写时也经常被要求给出。核心逻辑完全一样只是语法略有差异class Solution: def nextPermutation(self, nums: list[int]) - None: Do not return anything, modify nums in-place instead. n len(nums) i n - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: j n - 1 while j 0 and nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] left, right i 1, n - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1Python 里交换两个元素可以直接用nums[i], nums[j] nums[j], nums[i]不用借助临时变量。此外力扣的函数签名里nums是list[int]不需要返回值因为它要求原地修改。这一点和 JavaScript 版的return nums不同别看是小区别面试时被问“为什么不需要 return”也常常是考察点。时间复杂度方面三步操作都是单次线性扫描整体是 O(n)。空间上只用了常数个临时变量满足题目的 O(1) 要求。这也是这道题最让人舒服的地方思路一旦打通代码非常短性能还极其优秀。4. 面试场景与高频考点4.1 面试官可能会问的追问这道题在面试中出现的频率非常高而且面试官往往不会满足于你写出代码还会顺着往下追问。我整理了几个高频追问方向你可以提前准备。第一个常问的是“你能解释一下为什么交换后直接反转就能得到升序吗”这个问题考察的是对算法本质的理解。原因在于i 右侧原本是一个降序序列我们找 j 的时候是从右往左找第一个大于 nums[i] 的元素它实际上是右侧序列中从右往左数第一个“比 nums[i] 大”的数。交换 nums[i] 和 nums[j] 之后nums[j] 原来的位置被一个比它小的数占据而右侧其他元素的大小关系没有变整个右侧仍然保持降序。所以反转后得到的就是升序也就是最小的后缀排列。第二个常问的是“如果数组中存在大量重复元素这个算法还成立吗”答案是成立。关键在于比较条件里用了和把相等的情况当作“不可用”处理保证找到的永远是最靠右的可调整位以及右侧严格大于目标值的最小元素。第三个问题是开放性的“你能计算出任意排列在全排列中的排名吗”这涉及到康托展开是一个更深入的数学话题。虽然力扣第 31 题本身不要求这个但如果面试官想考察你的延展能力可能会从这里切入。我的建议是先把 nextPermutation 本身讲透再提一句“连续调用 n 次可以得到第 n 个后续排列也可以反过来设计 prevPermutation”这样展示出的思维深度会明显不一样。4.2 相关题目与变体迁移刷题最忌讳的是“一题一题孤立地刷”。这道题虽然短小但它像一条线索串联起好几道经典题目把它们放在一起看效率会高很多。先说最直接相关的力扣 46 题“全排列”和 47 题“全排列 II”。46 题要求输出所有排列47 题是含重复元素的版本。如果理解了 nextPermutation完全可以用它来生成全排列先排序得到最小排列然后不断调用 nextPermutation直到回到最小排列为止。相比回溯法这种方式写起来更简洁思路也更接近“字典序生成”的语义。还有一道很有意思的变体力扣 556 题“下一个更大元素 III”。它本质上就是第 31 题的“数字版”给定一个正整数 n找出由相同数字组成的、大于 n 的最小整数。做法就是把 n 转成数组跑一遍 nextPermutation再把数组转回数字检查是否越界。这道题我在面试中见过好几次它考察的其实是同一套能力能否把陌生问题抽象成已经做过的经典题。更进一步可以思考如何写出“上一个排列”prevPermutation。实现方式完全对称从右往左找第一个降序对nums[i] nums[i 1]在右侧找小于nums[i]的最大元素交换再把右侧反转。写一遍 prevPermutation你对字典序排列的理解会再深一层。4.3 刷题策略如何把一道题刷出十道题的效果很多人在热题 100 上刷题往往追求“数量”今天刷 5 道、明天刷 8 道但过两周回头一看全忘了。这是非常普遍的误区。我个人更推荐“围绕核心题做刻意练习”每做完一道有价值的题就主动去找它的变体、追问和相似题。以第 31 题为例一个完整的学习闭环应该包含四层第一层能独立写出 nextPermutation 并解释原理。第二层能快速套用到 556 题这类数字版题目上。第三层能说出它与全排列生成的联系并手动推导几个排列的字典序顺序。第四层能扩展到 prevPermutation 以及排列排名康托展开。做到第三层和第四层这道题在你脑子里就不再是一个孤立的代码片段而是一张可以随时调用的知识网络。面试时哪怕面试官换一个包装你也能一眼看出内核。5. 常见错误与排查技巧实录5.1 高频错误速查表这道题代码不长但新手容易出错的地方反而很集中。我把常见错误整理成一张速查表方便你写完代码后逐项对照检查。错误类型错误写法正确写法后果第一步比较符错误nums[i] nums[i 1]nums[i] nums[i 1]重复元素场景下无法找到正确的可调整位可能输出错误结果第二步比较符错误nums[j] nums[i]nums[j] nums[i]可能选中等于 nums[i] 的元素交换后排列不增反减忘记反转交换后直接返回必须反转 i1 之后的子数组后缀仍然降序导致得到的不是字典序意义上的“下一个”反转区间错误left ileft i 1把已经调整好的 nums[i] 也反转了结果完全错乱i 初始值错误let i n - 1let i n - 2需要比较 nums[i] 和 nums[i1]所以 i 最右只能到 n-2这份速查表里的几类错误我在实际调试中都踩过。最隐蔽的是第一个因为测试用例如果全是无重复元素和结果一模一样只有遇到[1, 1]这种用例才会暴露。5.2 实测排查方法小数据穷举验证如果写完代码不确定是否正确有一个非常实用的小技巧写一个暴力生成全排列的函数和小数据规模下跑 nextPermutation 的结果做对比。具体做法是对于长度为 1 到 6 的数组穷举所有排列并排序然后依次调用 nextPermutation检查每次返回的结果是否和排序后列表中的下一项一致。只要小规模全部通过算法在逻辑上基本就是正确的。这个验证方式能帮你快速定位是思路问题还是实现问题尤其是在处理重复元素的时候暴力对照法几乎是最好的调试工具。我自己刷这道题时就是先用暴力方法验证了[1, 1, 5]这些容易出错的重复元素用例才发现比较符的问题。如果你也在调试建议不要只盯着力扣自带的那几个示例手动构造一些边界用例完全升序、完全降序、全相同元素、最大长度数组覆盖住所有分支。5.3 我的个人心得最后分享一点体会。这道题最奇妙的地方在于它把“字典序”这个偏数学的概念变成了一个特别具象的工程问题找降序边界、找交换对象、反转后缀。每一步单独看都特别简单但组合在一起就是一套完整的算法。这让我想起写代码时的一个规律——真正优雅的解法往往不是因为用了什么高深的数据结构而是因为看问题的角度对了把复杂的全局问题简化成了几个局部的操作。我经常和刷题的朋友说第 31 题“下一个排列”是值得背下来的少数题目之一不是因为它答案短而是因为它代表了“字典序排列”这一类问题的标准范式。吃透它再去碰全排列生成、排列序列、下一个更大元素这些题你会发现自己几乎不用重新学都是在做同一件事的排列组合。
