做过 LeetCode 的朋友应该对这道 31 题印象很深不给你额外空间只让你原地操作数组找出字典序意义上的“下一个排列”。光看题面很容易懵但一旦理解了字典序排序的规律这道题的代码其实不外乎三四个分支而且半年后你大概率还能记得怎么写。这篇文章我就把这题从底层逻辑到边角细节完整拆一遍顺便聊聊我刷题时踩过的坑和总结的解题模板。1. 题目分析与核心思路1.1 先搞清楚“下一个排列”到底在问什么题目给的是一个整数数组比如[1,2,3]要你返回它在所有排列中按字典序排列后的下一个状态。所谓字典序你可以直接理解成“像查英语字典那样从左到右逐位比较大小”[1,2,3] [1,3,2] [2,1,3]。整数数组的字典序排序本质就相当于把这些数字看成字符串按字符比较。如果你把所有排列按从小到大列出来会发现它们是一棵清晰的排序树。比如三个元素[1,2,3]的全部排列是1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1题目要你做的就是把某个状态改成排在它后面一位的那个。比如输入[1,3,2]要输出[2,1,3]输入[3,2,1]已经是最后一个排列这时候题目规定要回到字典序最小的状态也就是整体升序的[1,2,3]。这个题有意思的地方在于它不需要你列出所有排列再查下一个而是要求直接在原数组上通过规则变换得到结果时间复杂度还要求是 O(n)。这意味着你必须理解字典序生成的数学规律而不是暴力枚举。1.2 字典序变换的核心规律最后一个上升沿我的理解方式是这样的假设当前排列是[1,3,5,4,2]它的下一个应该是多少先直观地想我们希望“尽量保持高位不动只在低位做调整”因为只有这样才能得到字典序刚刚好大一点的那个排列。从右往左扫描找第一个满足a[i] a[i1]的位置。在这个例子里从右往左看2 4不对是4 2继续往前5 4继续往前3 5找到了i 1。这个i就是“最后一个上升沿”。它决定了整个数组里我们可以自由调整的边界i左边的元素都已经处于“局部最大状态”不能动了i位置的元素是唯一可以变大的高位。而i右边的部分一定是一个单调递减序列否则就会在更靠右的位置找到上升沿。接下来要在i右侧找“比a[i]大的最小元素”用它和a[i]交换。为什么是“比它大的最小”因为我们要让i位置的增长幅度尽可能小这样整排列才最贴近当前排列。右侧是降序所以从右往左找第一个大于a[i]的数就是最小的那个。在例子里右边[5,4,2]中大于3的数从右往左依次是4和5最小的是4位置j 3。交换a[1]和a[3]得到[1,4,5,3,2]。交换之后i右侧仍然保持降序但我们需要的是紧随当前排列的最小后缀所以直接把右侧反转变成升序[2,3,5]。最终结果就是[1,4,2,3,5]。整个过程可以浓缩成三句话找最后一个升序对交换成稍大的头部把尾部反转成最小后缀。这同时也是 C STL 中next_permutation的实现逻辑。1.3 为什么从右往左找而不是从左往右很多初学者会问能不能从左往右扫描不行。字典序的关键在于“低位优先调整”越靠右的位置对字典序的影响越小。我们希望找到一个位置i使得i右边已经无法通过调整变得更大而i本身还可以增大。从右往左找最后一个上升沿本质就是在确认“右边已经到达最大状态”的前提下找到第一个可增大的高位。我习惯用一个类比这就像调整一个数字密码锁你会优先转动最右边的轮盘只有当所有右侧轮盘都无法再增大时才会去拨动左边一位。从右往左找正好是从最低有效位开始排查。2. 代码实现与复杂度分析2.1 标准解法流程伪代码级别我把这道题的标准解法拆成四步每一步都有明确的目的第一步特殊判断。如果数组长度小于等于 1直接返回因为只有一种排列无所谓“下一个”。第二步从右往左找i直到i 0且a[i] a[i1]。如果找不到说明整个数组是严格降序的已经是最大排列直接整体反转即可。第三步在i右侧从右往左找j直到找到第一个a[j] a[i]。由于右侧是降序这个就是从右往左遇到的第一个大于a[i]的值也就是右侧所有大于a[i]的元素中最小的那个。第四步交换a[i]与a[j]然后把i1到末尾的所有元素反转成升序。这四步做完数组就被原地修改成了下一个排列。这里有个关键点转换过程中右侧为什么可以直接反转而不是排序原因在于第二步找到的i是“最后一个上升沿”所以i1到末尾一定是一个非严格递减的序列。交换之后由于a[j]是右侧大于a[i]的最小元素所以交换后的右侧仍然保持降序。降序反转就是升序这就是字典序最小的后缀不需要调用任何排序函数。2.2 代码实现Python、Java、C 三版对照这里我给你三种主流语言的参考实现。逻辑完全一致只是语言细节有差异。Python 版本def nextPermutation(nums): n len(nums) if n 1: return i n - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: j n - 1 while 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 - 1这里有个小坑Python 中如果直接nums[left:right1] reversed(nums[left:right1])也行但面试时最好用双指针原地交换避免让面试官觉得你依赖语言切片特性。另外注意条件里的和这个直接决定了含重复元素时程序的正确性。Java 版本class Solution { public void nextPermutation(int[] nums) { int n nums.length; if (n 1) return; int i n - 2; while (i 0 nums[i] nums[i 1]) i--; if (i 0) { int j n - 1; while (nums[j] nums[i]) j--; swap(nums, i, j); } reverse(nums, i 1, n - 1); } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } private void reverse(int[] nums, int l, int r) { while (l r) { swap(nums, l, r--); } } }C 版本顺便看看 STL 是怎么实现的class Solution { public: void nextPermutation(vectorint nums) { int n nums.size(); if (n 1) return; int i n - 2; while (i 0 nums[i] nums[i 1]) --i; if (i 0) { int j n - 1; while (nums[j] nums[i]) --j; swap(nums[i], nums[j]); } reverse(nums.begin() i 1, nums.end()); } };如果你用过 STLstd::next_permutation的内部逻辑和这个基本一样只是它额外做了返回值判断告诉我们是否存在下一个排列。C 标准库里没有用sort来排尾部就是用reverse可见官方也认为这段尾部必然降序。2.3 时间复杂度与空间复杂度时间上最坏情况是数组完全降序比如[5,4,3,2,1]找i要遍历整个数组再加上反转也要遍历一次所以是 O(n)。正常情况更是严格小于 O(n)。这个复杂度保证了大数组也能高效运行符合 LeetCode 对这道题的要求。空间上全程只用常数个临时变量没有额外数组空间复杂度是 O(1)。这一点是题目明确要求的“不使用额外空间原地修改”所以任何想复制数组再排序的方案从一开始就不合格。我实测过在 Python 环境下n 10^5级别的数组这个解法运行时间基本在几毫秒量级瓶颈主要来自反转那一下。总体来看这道题的复杂度没有优化空间O(n) 和 O(1) 已经是理论上的极致。3. 边界情况与常见问题实战3.1 最容易踩的坑重复元素处理这道题最典型的坑就是数组里含有重复元素时比较符号写错。比如[1,5,1]正确的下一个排列是什么先把所有排列列一下[1,1,5]、[1,5,1]、[5,1,1]所以[1,5,1]的下一个应该是[5,1,1]。如果找i时用nums[i] nums[i1]而不是那i会找到1和5的位置因为1 5这个没错但找j时如果用nums[j] nums[i]而不是就可能找到等于1的那个元素导致交换后得到[1,1,5]这是“上一个排列”方向反了。关键在于字典序要求严格大于当前排列所以找j时不能用而是要用这样才能保证交换后i位置的数严格变大。找i时则相反必须用跳过相等的元素因为我们希望上升沿发生在最后一个严格上升的位置避免相等元素干扰。我记得有一次刷题输入[2,3,1]我把找i的条件写成了nums[i] nums[i 1]结果得到的答案是错误的。这个坑在面试里非常经典面试官很喜欢在重复元素的用例上做文章。3.2 特殊输入长度 0、长度 1、全降序数组长度 0 和长度 1 的数组不存在“下一个排列”的概念直接返回即可。这个判断必须在开头做否则后面的n-2会变成负数越界。全降序数组[3,2,1]表示当前已经是最大排列按题目规则要输出最小排列也就是升序[1,2,3]。这里注意找i的循环会一直执行到i 0才停止说明不存在上升沿。此时算法会跳过交换步骤直接把整个数组反转。反转的本质就是把降序变成升序正好满足要求。还有一种特殊情况是数组里所有元素都相等比如[7,7,7,7]它的下一个排列还是[7,7,7,7]。算法执行过程找i时因一路回退到 -1整体反转后数组保持不变。这个结果是正确的。3.3 我亲测的调试过程一个实际用例的手工推演下面记录一个我实际调试时用过的例子方便你对照代码逐步理解。输入[1,3,5,4,2]目标输出[1,4,2,3,5]。第一步从右往左找最后一个上升沿。从最右边开始4 2继续5 4继续3 5找到了i 1。这里为什么是3 5而不是5 4因为只有3的位置是“最后一个可以增大的位置”5和4已经在降序链上是局部最大值。第二步从右往左找第一个大于a[1]3的数。右侧是[5,4,2]从右往左看2 3跳过4 3找到j 3。为什么不选5因为4是大于3的最小值选它能让i位变化最小整个排列才最贴近当前状态。第三步交换3和4得到[1,4,5,3,2]。此时右侧[5,3,2]仍然是降序反转后变成升序[2,3,5]。最终答案[1,4,2,3,5]。整个过程我建议你也拿笔在纸上走一遍尤其注意交换之后右侧依然是降序这个性质是“直接反转”成立的前提。3.4 高频报错与修复速查表症状很可能的原因修复方式输入[1,3,2]输出[1,2,3]找j时用了导致交换后i位未严格变大改为nums[j] nums[i]跳过相等值输入[3,2,1]报数组越界没有处理n 1的边界开头加长度判断输出和预期的下一个排列不同找i时用了没有跳过相等元素改为nums[i] nums[i1]尾部排序用了sort复杂度变高没利用右侧单调降序的性质改为双指针原地reverse交换后再次调用函数结果错乱原地修改时引用了临时切片Python 中避免nums[:] ...的写法歧义使用显式交换3.5 换个角度思考如何用单调性规避重复扫描理论上找j的过程还可以进一步优化由于右侧是降序可以用二分查找在[i1, n-1]区间找到第一个大于nums[i]的位置。不过因为整体复杂度本来就是 O(n)二分与否对最终性能影响微乎其微我一般还是推荐从右往左线性扫描逻辑更直观也少写几行边界判断。如果你追求极致性能可以自己实现一个二分函数在降序数组中找“最后一个大于目标值”的元素。这个技巧在扩展题“下一个更大元素 III”里会用到因为那边涉及到对数字字符串操作二分能有效减少常数时间。4. 由这题延伸出去的东西4.1 全排列生成与回溯的关系很多同学学全排列时用的是回溯法先固定前缀再递归后缀然后撤销选择。而下一个排列算法提供了一种完全不同的视角给定一个排列你可以直接算出它的后继不需要递归不需要维护visited数组。这意味着你可以从一个初始排列开始反复调用nextPermutation按字典序生成所有排列。这在某些场景下比回溯更快比如迭代器式的排列遍历每调用一次生成一个空间占用始终是 O(1)。当然它也有局限如果初始状态不是最小排列你需要先找到“从哪个状态开始”。从工程角度看这种“给定状态求后继”的思想在很多地方都能用。比如 LeetCode 上的 60 题“排列序列”要求直接返回第 k 个排列它的核心思路就是用数学计算而不是枚举所有排列本质上和本题的字典序规律一脉相承。4.2 “下一个更大元素”的变体556. 下一个更大元素 III题目要求给定一个正整数n重新排列它的各位数字得到比当前数字大的最小整数。如果不存在返回 -1。这道题的输入是数字本身不是数组但你可以把每一位拆成数组然后直接套用本题的算法。唯一要注意的是结果可能超过 32 位整数范围需要判断溢出。LeetCode 官方给的示例是n 1234得到1243如果n 1999拆成数组后找i和j的过程和本题一模一样。这道题还有一个变种当输入数字本身已经是降序排列时比如4321不存在更大的排列返回 -1。这和本题“如果全是降序就反转成升序”的规则不一样需要额外判断。4.3 面试中如何用这道题展示水平面试遇到“下一个排列”时不要上来就背代码。我建议你先举一个实际例子比如[1,3,5,4,2]大声说出你打算怎么操作先找最后一个上升沿再找一个比它大但尽可能小的数交换最后把后面的降序翻成升序。说完规律再落代码。面试官通常还会追加一个问题“如果数组里有重复元素怎么办你的代码还正确吗”你要立刻指出找i时用跳过相等项找j时用确保严格大于这两处符号是重复元素场景下的关键。另外最好主动说清“为什么尾部直接反转不用排序”这能体现你真正理解了这个算法的数学性质而不是背了两个循环。4.4 手写一个基于该算法的排列生成器如果你想验证自己的理解可以写一个生成前 N 个排列的小函数。这里给出一个 Python 示例用nextPermutation作为核心迭代器def generate_permutations(arr): arr sorted(arr) yield arr[:] while True: n len(arr) i n - 2 while i 0 and arr[i] arr[i 1]: i - 1 if i 0: break j n - 1 while arr[j] arr[i]: j - 1 arr[i], arr[j] arr[j], arr[i] arr[i1:] reversed(arr[i1:]) yield arr[:]这个生成器会按字典序产出所有唯一的排列。给你一个数组[1,1,2]它能正确产出[1,1,2]、[1,2,1]、[2,1,1]不会产生重复项因为算法本身严格基于字典序找后继不会绕回同一个状态。5. 一点个人心得我第一次刷这道题时花了不少时间看别人的题解但总是记不住步骤。后来发现关键在于“最后一个上升沿”这个短语——只要你能在一分钟内说出“找最后一个上升沿再找右侧最小的更大值交换反转右侧”代码基本就不会写错。还有一个小技巧我在 LeetCode 上提交前会用几个特征用例测试[1,2,3]、[3,2,1]、[1,1,5]、[1,3,2]、[2,3,1]。这几个用例覆盖了普通情况、完全降序、重复元素、尾部降序但不完全有序等多种边界。每次把这几个用例跑一遍基本能确认代码没有硬伤。如果面试中你需要在白纸上手写代码我建议把swap和reverse单独写成两个辅助函数这样主流程看起来非常清爽面试官也容易跟着你的思路走。别贪图省代码因为越简洁的写法对边界的处理越隐晦反而容易出问题。做算法题就是这样真正理解了这五六个边界条件的来龙去脉同类问题就不再是背题而是变成了一种推导。这也是 LeetCode 热题 100 里我建议所有准备面试的人都优先吃透的这一道——它不仅考察数组操作更考察你对字典序和数学规律的抽象能力。