1. 问题拆解从“全排列的顺序”说起关于“31.下一个排列”这道题我想先聊一个看起来简单、但很多人第一次接触时都会卡住的问题计算机怎么理解“字典序”你可以把数组[1,2,3]的所有全排列按从小到大排成一个列表[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]这个列表里的顺序就是字典序。字典序的规则并不复杂两个排列从头开始逐位比较第 i 位数字更小的那个排列排前面。如果前几位完全相同就比较下一位直到分出大小。那么“下一个排列”要做的事情就是给定一个排列找出它在字典序中紧挨着的后一个排列。比如输入[1,3,2]下一个就是[2,1,3]。如果当前排列已经是字典序中最大的那个也就是降序排列比如[3,2,1]那就回到最小的排列[1,2,3]。这道题看起来只是一个原地修改数组的要求——题目明确要求不能申请额外空间只能用常数级别额外空间来完成——但它背后考察的其实是对“全排列生成顺序”的理解深度。如果你对字典序的生成规律不熟悉很容易一上来就想着先求出全排列再去找下一个虽然思路直观但复杂度完全无法接受全排列的时间复杂度是阶乘级别的。这道题想要的正解时间复杂度只有 O(n)空间复杂度 O(1)。我第一次刷到这道题的时候说实话第一反应也是“直接调库”。很多语言的标准库都内置了现成的下一个排列方法比如 C 里的next_permutationPython 里虽然没直接同名函数但组合工具里也有相关能力。但如果是面试场景或者需要在限定环境下手写实现理解库函数底层的原理就变得非常关键。这道题的价值就在于它强迫你把库函数背后的算法逻辑想清楚而不是永远当一个黑盒调用者。先说清楚目标读者这道题适合算法入门不久、正在刷数组/双指针类题目的人也适合已经开始接触回溯、但纠结于“全排列到底怎么来”的开发者。整道题一共就三步逻辑但每一步都有容易踩的坑。2. 核心规律的直觉建立从“降序后缀”说起要理解下一个排列的算法先得理解一个关键观察——降序后缀。我们看[1,5,8,4,7,6,5,3,1]这个排列。从右往左看末尾的[3,1]是降序[5,3,1]还是降序[6,5,3,1]依然是降序直到[4,7,6,5,3,1]这里4 小于 7降序被打破了。打破降序的这个位置就是整个算法的入口。为什么要特别关注“降序后缀”因为字典序的本质是“高位优先”。排列的高位越靠前它的权重大。我们要找到“下一个更大的排列”本质上就是要找到一个恰好比当前排列大一点点的排列。那么这个“大一点点”应该发生在哪一位答案是发生在最后一个“还有资格变大”的位置上。更准确地说是从右往左数第一个打破降序的位置。想要通过调整让排列变大又不希望变得太大就必须把调整点放在尽可能靠右的位置。我习惯用一个生活化类比来理解这件事——把它想成数字进位。比如数字123下一个数字是124变化发生在个位不是十位。因为个位是最低位的“调整点”往后再没有更低位了如果个位已经满到无法增加比如129下一个数字是130变化就发生在十位。永远从最低那一位尝试进位找不到可进位的位置再往更高一位看。排列也是类似的。全排列里“权重最低”的位置是数组末尾。末尾已经是降序时说明这个后缀里不存在更小的排列了——也就是说后缀已经到了它的最大形态。想继续变大必须把改动点往前挪打碎更靠前的降序。所以算法第一步一定是从右往左扫描找到nums[i] nums[i-1]的第一个位置i-1也就是第一个需要变大的位置。如果整个数组从右往左全是升序——等价于从左往右看是降序——那就说明这个排列本身已经是字典序最大的排列直接反转整个数组返回。这一步复杂度是 O(n) 的扫描但它同时给出了一个很重要的结论在i-1位置右侧的所有元素都是从大到小排列的也就是一个降序序列。这个结论是后续第二步选择交换对象的基础。也许有人会问为什么右后缀一定是降序因为i-1是第一个打破降序的位置意味着从末尾一路扫描到i每个相邻对都是nums[k] nums[k-1]等价于整个[i:]区间内严格降序。这个性质不是巧合而是扫描规则的直接结果后续反转操作的依据也正是这一点。3. 三步核心算法推导为什么是“交换反转”标准解法分为三步我先给出完整流程再逐条解释每个步骤背后的逻辑。第一步从右向左找到第一个nums[i] nums[i1]的位置i。如果找不到说明整个数组是降序排列的反转整个数组后返回。这里的i就是我们要调整的“低位进位点”。第二步从右向左找到第一个大于nums[i]的元素nums[j]交换nums[i]和nums[j]。这个步骤保证了交换后位置i上的值变大了而且变大的幅度是“刚好超过原来一点”的最小幅值。第三步将i1到数组末尾的区间反转。因为交换后该区间依然是严格降序反转成升序后它就是该区间元素能组成的最小排列保证整体“只多不少且增量最小”。三个步骤环环相扣缺一不可。3.1 第二步到底在找什么严格大于不是大于等于很多人第一次写代码时会把第二步写成“找到第一个大于等于nums[i]的元素”这是一个隐蔽的错误。为什么必须严格大于我们回顾第二步的目标在i位置右侧所有降序元素中挑选一个nums[j]与nums[i]交换。这个j是“从右往左”第一个大于nums[i]的元素本质上是在降序序列中找大于nums[i]的最小元素。如果降序序列中存在与nums[i]相等的元素而我们的循环条件写成了取到的就是相等的那个交换之后nums[i]完全没有变大后面反转升序出来的排列可能比原始排列还小这与“下一个更大的排列”的目标直接冲突。为什么会存在相等元素还影响结果关键在于交换后的后缀状态。我们用[2,3,1,3]这个例子来推演。从右往左扫描3 1i 1nums[i] 3。从右往左找第一个大于 3 的元素当循环条件写成严格大于时找到末尾的 3交换后[3,3,1,2]反转[1,2]得到[3,3,1,2]。但原始排列的字典序下一个应该是什么实际上原来的[2,3,1,3]后面确实应该直接跳到[2,3,3,1]。这里我举的例子如果改成[2,1,3,3]更直观降序后缀是[3,3]打破降序的位置是第二个元素 1右侧大于 1 的最小元素是 3交换后[2,3,1,3]再把[1,3]升序排成[1,3]得到[2,3,1,3]。如果第二步拿的是另一个 3结果也一样因为相等元素互换不影响排列内容但写代码时用大于等于条件仍然不严谨在存在重复元素的边界用例下可能出问题。更稳妥的实践是坚持“严格大于”语义清晰也符合算法定义。这个细节如果只是读题不实际写代码很难发现。我从个人经验出发建议在本地跑一个标准库函数和手写实现的对拍测试专门构造含重复元素的用例很快就能定位到这一处差异。3.2 第三步为什么要反转交换后后缀的固定形态交换完成之后数组形态是这样的在i1到末尾的区间内元素依然保持降序。为什么因为原始数组中区间[i1:]是降序这是第一步扫描得到的结论。第二步交换时nums[j]是从这个降序区间中取出的而nums[i]是从区间左侧插入到这个降序序列中的。因为nums[i]小于右侧所有大于它的元素中的最小值所以插入后这个区间从i位置处被拆开但拆开后的两段左边那段依然降序右边那段也依然降序且左边那段的所有元素都不小于右边那段的元素。换句话说[i1:]整体依然保持降序。举个例子[1,3,2]中i 1nums[i] 3。右侧降序后缀只有一个元素[2]但这一步内部并没有可见的交换复杂性。换一个更明显的例子[1,5,1]。扫描发现1 5i 1nums[i] 5。从右往左找第一个大于 5 的元素——不存在因为1不大于5。实际上对于[1,5,1]第一步找到的破降序位置是i1右侧区间是[1]从右往左找大于nums[i]的元素没有这一步不会进入。等等这里需要重新审视正确的前置条件是nums[i] nums[i1]。[1,5,1]中5 1所以第一步其实找不到i满足nums[i] nums[i1]直接进入反转流程结果是[1,1,5]。我的例子给错了。重新来。[2,3,1]从右往左1 3不成立3 1所以找到i 1nums[i] 3。右侧区间是[1]从右往左找比3大的元素没有这里就不对了因为[2,3,1]的下一个排列应该是[3,1,2]它的调整点应该是i 0而不是i 1。问题出在第一步扫描条件上找到的是第一个满足nums[i] nums[i1]的位置而不是满足nums[i] nums[i1]的位置。从右往左扫描要找的是“左边的数小于右边的数”这对关系比如[1,3,2]中1 3位置i 0就是调整点。所以扫描条件是nums[i] nums[i1]不是大于。上面示例中的语句应该改为[2,3,1]中从右往左1 3不成立3 1所以不满足条件直到2 3成立i 0调整点是数组首元素 2。我再整理一个完全正确的演示序列例子[1,2,7,4,3]第一步扫描从右往左3 4 不成立4 7 不成立7 2 不成立2 1 不成立不对顺序反了。从数组末尾开始比较nums[i] nums[i1]最后一个比较是nums[0]1和nums[1]2确实是1 2所以i 0。但直觉上调整点应该是数字 2 而不是数字 1因为后缀[7,4,3]整体降序[1,2]中的 2 才有资格变大。这里的问题是扫描应该从倒数第二个元素开始往前比较nums[i]和nums[i1]发现第一个升序的相邻对。[1,2,7,4,3]中相邻对从右往左依次是(4,3)降序(7,4)降序(2,7)升序找到i 1也就是数字 2。这才是正确的调整点。交换从右往左找第一个大于 2 的元素依次找到 3交换得到[1,3,7,4,2]。反转i12到末尾[7,4,2]反转后[2,4,7]最终结果是[1,3,2,4,7]。而[1,2,7,4,3]的字典序下一个确实应该是[1,3,2,4,7]。手写验证以[1,2,...]开头的排列中1,2,7,4,3是1,2前缀下最大的排列因为后缀已降序。下一个只能提升第二个位置到 3后缀取最小[2,4,7]得到1,3,2,4,7。完全吻合。3.3 三个步骤的复杂度账每一步都只有一次线性扫描或一次线性反转整体时间复杂度是 O(n)额外只用了常数个变量空间复杂度 O(1)。这个复杂度意味着即使数组长度达到百万级别也能在极短时间内完成计算。对比暴力做法先枚举所有排列排序后查找当前排列再取后面一个时间复杂度至少 O(n!)空间复杂度 O(n!)完全不可用。理解这道题的正解本质上就是理解了为什么不需要枚举也能定位下一个排列。4. 代码落地C / Python 双语言实现与细节打磨在这一节里给出手写实现的最佳实践。4.1 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]); } // 反转降序后缀为升序 reverse(nums.begin() i 1, nums.end()); } };有三处细节值得展开。第一i的初始值是n - 2从倒数第二个元素开始这样才能比较nums[i]和nums[i1]把最后两个元素包含在扫描范围内。第二第一步扫描条件用nums[i] nums[i 1]。等号是必须的。如果相邻两个元素相等从字典序角度看它们不构成严格升序因此不应当在这里设置调整点。比如[1,1,2]从右往左扫描2 1不满足停在了i 1的位置这里的调整是数字 1第二个变到 2得到[1,2,1]验证正确。如果没有等号条件写成同样这个例子里因为1 2也会停下来结果一致。但考虑[1,2,2]从右往左2 2带等号时条件成立继续左移1 2停止i 0从右找第一个大于 1 的元素是 2最右边的交换后[2,2,1]反转后缀[2,1]为[1,2]得到[2,1,2]这是正确的。如果不带等号[2,2]的相等关系会被误判成升序导致i 1交换后[1,2,2]反转空后缀结果还是[1,2,2]没有推进。所以等号不仅不能省略而且是关键。第三第二步扫描条件用nums[j] nums[i]同样必须带等号。在降序后缀里跳过相等的元素从右往左找的第一个严格大于nums[i]的元素就是最靠近右端的大于元素。如果是找“最小的大于元素”但降序后缀中更大的元素反而在左端。这里需要想清楚为什么从右往左遇到的“第一个大于”就等于“最小值大于”因为降序后缀从右到左是递增的。例如[7,4,3]从右往左是 3、4、7逐渐变大。从右往左找第一个大于 2 的元素先看 33 2直接命中。3 确实是降序后缀中大于 2 的最小值。假如没带等号遇到等于nums[i]的元素时会停下然后把一个相等的数交换到前端不仅没有让排列变大还会破坏后缀的有序性得到错误的排列。所以等号的意义是跳过相等项确保命中的是“严格大于且最小”。4.2 Python 实现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重新赋值成另一个列表。如果写成nums reversed(nums)之类在函数外看到的nums并没有变化因为只是让局部变量指向了新的对象。要确保修改的是传入列表本身必须对列表元素逐个赋值或者用切片赋值。切片赋值nums[:] ...也可以但手写双指针反转更符合算法原意。4.3 为什么手动反转而不是直接调用排序有人可能问第三步用sort行不行排序确实能把降序后缀转换为升序但排序的时间复杂度是 O(m log m)其中 m 是后缀长度。手工反转只需要 O(m) 时间而且后缀已经被前面步骤保证是降序的反转比排序更精准地利用了信息。另一个角度是反转是在已知“必然降序”的前提下进行的。如果某个实现不在交换后保持降序性质那反转就会失效所以反转也反过来验证了前面两步执行的正确性。这是一个很好的自检思路如果反转后缀后结果还是错回头检查前两步是否破坏了降序结构。5. 常见问题与排查技巧实录刷题时最容易出问题的几个点我整理成速查表每个都是我实际在运行和调试中遇到过的。问题现象常见原因排查方法输入[3,2,1]输出不是[1,2,3]第一步没判断i 0直接对不存在的i做交换或反转检查if (i 0)是否只包裹交换逻辑反转逻辑是否在其外输入[1,1,5]结果变成[1,1,5]或错误排列第一步或第二步遗漏等号重点排查和单独跑重复元素用例输入[1,3,2]结果变成[2,3,1]而不是[2,1,3]第三步没有反转后缀检查反转区间是否写成了[i1:]而不是[i:]输入[1,2]结果没变化第一步错误地从i n - 1开始确认i初始化为n - 2输出正确但提交超时使用了全排列或排序方案确认只有一次线性扫描和一次线性反转5.1 一个隐蔽的边界单个元素数组nums [5]n 1i初始化为-1第一步循环直接跳过i 0所以不进入交换直接反转从i10到末尾也就是整个数组。反转长度为 1 的数组结果还是[5]。从语义上讲单个元素的排列只有一个它的下一个就是它自己。这个行为是合理的。但有些实现里如果反转函数写的是reverse(nums.begin() i 1, nums.end())在 C 中如果i 1等于nbegin() n是合法的尾后迭代器反转区间为空也没有问题。Python 中切片[i1:]或反转区间的双指针也要注意索引不要越界。5.2 对拍测试让两个实现互相验证我想分享一个平时刷算法题很实用的做法在本地用标准库实现和手写实现做对拍。比如在 Python 中可以先用itertools.permutations生成所有排列按字典序排序然后对每个排列调用手写函数验证得到的结果与排序列表中下一个元素是否一致。在 C 中直接用标准库的next_permutation与手写实现对比。对拍时一定要覆盖这些类型升序数组[1,2,3,4,5]降序数组[5,4,3,2,1]有重复值[1,2,2,3]、[2,2,2]长度极小[1]、[1,2]、[2,1]后缀完全降序且长度大于 2[1,4,3,2]全局降序但首尾相接[2,1]对拍逻辑非常简单import itertools def brute_force(nums): perms sorted(set(itertools.permutations(nums))) idx perms.index(tuple(nums)) return list(perms[(idx 1) % len(perms)])对拍是我自己排查第三类问题[1,3,2]变[2,3,1]时最快定位的手段。手写实现丢进去对拍一轮几百个用例跑下来错误模式会非常明显。5.3 替代思路辨析为什么“暴力 剪枝”不可取有人可能想既然全排列能解决为什么不在生成时记录当前排列的位置提前终止这确实是一种“笨但正确”的解法。但注意题目要求原地修改而且全排列的生成过程本身就需要 O(n!) 次递归。即使剪枝找到当前排列之后还要生成下一个而下一个排列和当前排列之间可能隔着大量不必要的组合。在数据规模较大时这种方法会超时。正确解法是词典序生成排列的数学性质直接推导的从原理上绕开了枚举。6. 从一道题到一类题字典序算法的应用价值这道题看起来只是刷题实际上字典序下一个排列的思想在现实开发中到处可见。6.1 全排列生成与回溯剪枝优化生成全排列最典型的方式是回溯。但如果要求按字典序输出所有排列而且需要在生成过程中跳过某些不满足约束的排列那么理解“下一个排列”的数学规律可以帮你直接跳转而不是逐一遍历。例如某个场景下只需要第 k 个排列可用康托展开Cantor Expansion直接算出第 k 个排列的元素分布而它的逆过程依赖的正是“剩余元素按字典序排列”的规则与本题第三步反转后缀的思路一脉相通。第 k 个排列的问题我的个人经验是先用小规模数据手算一遍康托展开再对照代码看每一步减掉的数量是怎么来的。很多教程直接丢公式看完了照样不会写。搞懂本题的降序后缀后再回头理解康托展开会顺畅很多。6.2 数组元素组合的下一个状态在一些业务系统中需要遍历一个集合的所有组合或排列状态比如排课表中的教师分组、抽奖活动的号码排列规则、问卷题目的选项顺序轮换等。字典序的下一个排列算法提供了一种无状态、无碰撞的遍历方式只要记住当前排列就能算出下一个。不需要存储整个状态空间也不需要在内存中维护一个巨大的全局表。6.3 降序后缀的巧用下一个更大的整数LeetCode 平台上有一道“下一个更大元素”系列题与本体的区别在于一个是数组间的位置关系一个是整体排列的大小关系。另有一道“数字组合中的下一个更大整数”变体题比如给定整数123857找出用相同数字组成且大于该数的最小整数。这个变体的本质就是本题把整数拆分成数组执行一次nextPermutation再拼回去。一遍过这个变体题时就懂了本题的跨界应用价值。6.4 面试时的思考路径展示面试官拿到这题看重的不一定是能默写代码而是能否通过观察降序后缀推导出交换策略。我在不同场合模拟面试时发现有一种表达比较加分——先讲“我需要找到一个尽可能靠右的、还能变大的位置”再说明“右侧降序意味着该后缀是最大形态”再解释“交换右侧大于当前位的最小元素让当前位恰好变大”最后说“反转后缀变成升序才能让全局最小”。这样四步讲下来既有原理推导也有操作动机比上来直接背代码清晰得多。7. 实操总结与最后叮嘱这道题我前前后后刷过多遍每次的体会都不太一样。最初只是记住“三步走”后来在重复元素用例上栽过跟头再往后才真正理解每一步的数学依据。这里分享几个我个人的实操习惯。第一写代码时把第一步循环的终止条件拆开想清楚。i最后停下来的位置有两种情况要么找到一个合法的升序邻接对要么i从-1越界退出。后面无论是交换还是反转都依赖这个状态。最好在测试用例中同时覆盖这两种情况确保它们各自走得通。第二反转区间千万别写错。很多人会下意识写reverse(nums[i:])把nums[i]也包含进反转范围结果整个排列推翻重来。正确范围是从i 1开始。记住调整点本身是已经变大过的数不需要动要动的是它右边的降序大尾巴。第三在本地调试时用重复元素构造用例。不要只盯着[1,2,3]这种理想输入现实中的数据几乎都会带重复。[1,1,2]、[2,2,2]、[2,2,3,1]这几个用例能测试到等号条件的全部分支。我自己是把这三个用例写进测试文件固定跑的任何修改后先跑一遍确认没问题再提交。第四如果面试时被要求分析复杂度不要只说 O(n) 和 O(1)。面试官想听到的关键词是“一次线性扫描”“常数级别额外变量”“降序后缀的反转是线性操作”。把这些结论和代码步骤逐一对应起来会比背诵复杂度结论更有说服力。这道题还有一个不太起眼但很重要的知识点为什么反转后缀后一定能得到“最小后缀”因为降序后缀反转后就是升序升序排列是该区间元素能组成的最小排列。而区间元素集合在交换前后保持不变只是排列顺序变了。所以这个反转操作既保证了下一个排列存在也保证了它是“最小”的增长量。最后再分享一下对拍工具的具体用法先把标准库实现写成一个独立函数打印出每一步的结果用手写实现逐步比对。如果某个用例两个函数输出不同缩小数组长度到 3 到 4 个元素手动穷举全部排列找出首个不一致的位置基本一眼就能看出是等号问题还是反转范围问题。这种排查方式比盯着代码死看效率高得多。本题的代码量不大但信息密度不小。真正吃透它全排列、字典序、康托展开这些相关概念都会跟着清晰起来。如果你正在刷算法题建议把这道题和回溯全排列的题目放在同一天练习互相印证理解。我实际试下来双题组合练比单独刷一道记忆效果要好很多。