我最早刷到这道“下一个排列”的时候其实是在面试前突击准备算法题。当时第一眼看到题目描述觉得挺简单不就是找一个比当前排列大一点的排列吗结果动笔一写才发现这题本质上考的是对字典序的理解、对数组规律的观察以及“如何在不引入额外空间的情况下完成一次精准的调整”。它不止频繁出现在 LeetCode 热题 100 里在真实面试中也是出场率很高的中等等级题目。更关键的是这道题的解题思路可以直接迁移到“全排列生成”“第 k 个排列”“字典序排名”等一系列问题上。这篇题解不打算只给你抄一遍代码。我会把这道题的推导过程、边界情况、常见错误、调试技巧统统拆开来讲配合具体数组示例一步步走一遍最后再聊聊它的变式和应用。无论你是在准备校招、社招还是单纯想补一补排列组合的算法功底这篇文章都能让你把“下一个排列”真正吃透。1. 题目拆解先说清楚什么是“下一个排列”1.1 字典序是什么意思这道题的核心概念是“字典序”lexicographical order。听起来高大上其实就是你在英文词典里查单词的那种顺序先比第一个字母如果相同再比第二个依次类推。比如 “abc” 和 “abd”前两个字母都是 a、b第三个字母 c d所以 “abc” 排在 “abd” 前面。放到数字排列里也是一样的规则。我们把一个数组像字符串一样从左到右比较比如[1,3,2]和[1,2,3]第一个元素都是 1第二个元素 2 3所以[1,2,3]排在[1,3,2]前面。那么“下一个排列”就是指在字典序中比当前排列大的那些排列里面最小的那一个。如果当前排列已经是字典序中的最大排列也就是所有元素按降序排列比如[3,2,1]那它就没有下一个排列了此时题目要求把它重新排成最小的排列[1,2,3]。理解这一步非常重要因为很多人会误以为“下一个排列”只是“交换相邻两个数”或者“找到一个稍大的数换过来”。实际上它必须是比当前排列大的所有排列中最小的那个这个限定词“最小”才是整个算法的关键约束。1.2 为什么这个题值得花时间研究我见过不少同学跳过这道题理由是“太偏了面试不会考”。但实际上我在面试中至少遇到过三次和它直接相关的题目一次是原题一次是“输出下一个更大的数用数组表示”还有一次是“给定一个排列求它在所有排列中的排名”。前两个都需要“下一个排列”的核心思想第三个也需要借助“下一个排列”的生成逻辑来推导。另外这道题也是深度理解递归和回溯的很好的引子。你如果写过全排列的递归解法会发现回溯法天然就是在“字典序”中生成排列的。理解“下一个排列”相当于从另一个方向切入不递归不回溯只用数组原地操作就能从一个排列直接跳到字典序中的下一个状态。这种“跳转”的思路在解决很多组合数学问题时特别有用。1.3 看一眼题目限制信息量很大题目通常会给出这样的约束n nums.length1 n 1000 nums[i] 100。从这些约束里我们能读出几个关键信息n 最小为 1所以长度为 1 的数组要单独想清楚它的下一个排列就是它自己。n 最大为 100这个规模很小就算用 O(n²) 的暴力方法理论上也能跑完但题目要求“原地”修改并且进阶要求是 O(1) 额外空间这就意味着我们不能开一个新数组排序或存储。元素范围是 0 到 100存在重复值这一点非常重要。有重复值的情况下字典序的定义依然成立但我们在实现时要特别注意相等元素的处理。边读题边把这些限制圈出来其实就已经能看出这道题考察的不只是“能不能想出思路”还包括“能不能写出干净、不出错、不越界的实现”。2. 核心思路从“字典序”出发推导出经典三步2.1 观察一个具体排列找到变化规律我们直接用一个例子来推。假设数组是[1, 5, 8, 4, 7, 6, 5, 3, 1]我们想找到比它大一点点的下一个排列。先别急着想算法我们人肉来找。字典序比较两个排列时是从左往右找第一个不同的位置。如果我们要构造一个比当前排列更大的排列就需要从右边开始找一个能“变大”的位置。这个位置越靠右变化幅度越小得到的排列就越接近当前排列。那我怎么判断哪一位可以变大我们把数组从右往左看1 - 3 - 5 - 6 - 7 - 4 - 8 - 5 - 1。从右往左发现1 3这是一个上升的趋势3 5还是上升5 6仍然是上升6 7继续上升7 4到这里趋势中断了。也就是说[7, 4, ...]这一段是从左往右降序的而更右边[4,7,6,5,3,1]是从某个位置开始左边比右边小然后后续呈递减。我们找的是什么是从右往左第一对满足nums[i] nums[i1]的相邻位置。在这个例子中站在 i 3也就是数字 4这里nums[3]4nums[4]74 7这是第一对从右往左出现的“升序对”。为什么一定要从右往左找因为越靠右的位置对排列大小的影响越小。我们要找“最小的更大变化”当然优先动最右边的位置。找到 i 之后说明什么说明位置 i 右侧的所有元素[7,6,5,3,1]是降序排列的。降序排列是这一段里字典序最大的状态所以它不可能通过调整内部顺序变得更大只能动位置 i 本身。2.2 为什么找到“升序对”之后要交换“右侧最小大数”现在位置 i 上的数是 4它右侧的段是[7,6,5,3,1]这是一个降序段。为了得到“比当前排列大但又是最小的”我们得把 i 位置的数变大而且要变大的幅度尽量小。怎么变从右侧降序段里找一个比 4 大的最小数。右侧段里比 4 大的数有 5、6、7其中最小的是 5。我们找到它位置在 j 6然后把 nums[i] 和 nums[j] 交换。交换后位置 i 变成了 5右侧段变成了[7,6,4,3,1]。有人会问为什么不直接交换 4 和 7因为 7 虽然比 4 大很多但这样一来位置 i 变得太大整个排列的增大幅度就太大了不符合“最小增长”的要求。选 5 才是最小的增大这是这一步的直觉来源。交换完之后位置 i 右侧还是降序[7,6,4,3,1]。但是注意位置 i 已经比原来大了那么为了让整个排列“尽可能小”右侧这段应该被变成升序也就是最小的字典序状态。降序段反转后就变成了[1,3,4,6,7]。最终得到[1, 5, 8, 5, 1, 3, 4, 6, 7]。我们可以验证一下这个排列比原来的[1,5,8,4,7,6,5,3,1]大而且在所有比它大的排列里它的变化幅度最小。因为只动了尽可能靠右的位置而且右侧剩余部分被整理成了最小的升序状态。2.3 经典三步走找、换、翻到这里算法已经呼之欲出可以总结成三个步骤第一步从右往左扫描找到第一个满足nums[i] nums[i1]的位置 i。如果找不到说明整个数组是降序排列已经是字典序最大的排列直接把整个数组反转成升序返回。第二步在 i 右侧从右往左扫描找到第一个比 nums[i] 大的数 nums[j]因为右侧是降序所以从右往左第一个大于 nums[i] 的数必然就是大于 nums[i] 的最小值。交换 nums[i] 和 nums[j]。第三步把 i1 到数组末尾这一段整体反转因为这段当前是降序反转后变成升序得到字典序最小的状态。这三步缺一不可。只做第一步和第二步右侧的降序段会让整个排列不是最小的大排列只做第一步和第三步位置 i 没有变大排列甚至可能变小只做第二步不选最小的比 nums[i] 大的数增长幅度就不是最小。这套思路的本质是“字典序下一个状态的生成”。想通之后你会发现它与递归全排列里的“剪枝”“回溯”有奇妙的一致性回溯法生成全排列时就是在每一个前缀固定后让后缀从小到大排列而“下一个排列”就是找到最后一个还能增大的前缀位置然后重组后缀。3. 实现细节写出优雅且不易出错的代码3.1 边界情况一数组长度只有 1长度为 1 时[x]的字典序中既没有比它大的排列也没有比它小的排列下一个排列就是它自己。用三步走来看从右往左扫描根本找不到nums[i] nums[i1]因为只有一个元素循环进不去。此时按照规则应该反转整个数组反转后还是自己所以直接返回即可不需要特判。不过很多标准答案里会单独写一个if (n 1) return;之类的早退这主要是为了代码可读性和避免后续逻辑越界从实现角度看并非必需。我个人的建议是如果你在面试中写代码加上这个特判会让面试官觉得你考虑问题更全面哪怕逻辑上不加也不会出错。3.2 边界情况二数组里有重复元素重复元素是这道题最容易踩坑的地方尤其是第二步“找比 nums[i] 大的数”。比如[1, 5, 8, 5, 4]从右往左找第一对升序对i 指向第一个 5下标 1右侧是[8,5,4]这是一个降序段。降序段里有比 5 大的数吗有 8还有一个 5和 nums[i] 相等。我们要找的是“大于 nums[i] 的最小数”所以只能选 8不能选 5因为 5 不大于 5。第三步反转也需要留意右侧降序段里如果有重复元素反转后依然是升序不需要额外处理相等元素。例如[1,5,8,5,4]交换后变成[1,8,5,5,4]右侧[5,5,4]反转变成[4,5,5]最终结果是[1,8,4,5,5]完全正确。还有一种情况整个数组所有元素都相同比如[2,2,2]。从右往左找不到任何nums[i] nums[i1]因为全是相等所以直接反转。反转后还是[2,2,2]这个结果是正确的因为所有排列都相同下一个排列就是它自己。3.3 代码实现以第一个大于 nums[i] 的数作为关键我用类 C 的伪代码写一遍核心逻辑方便大家直接对照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()); }这段代码里有几个细节值得抠一下第一个细节找 i 的循环条件用的是nums[i] nums[i1]这里一定要带等号。如果数组右侧存在相等元素比如[1,2,2,3]从右往左扫描3 2不满足2 和 2 相等满足继续左移2 和 1 比较1 2停下。这时 i 指向 1这是正确的。如果你不小心写成了num[i] nums[i1]相等的情况会被当成候选 i导致后续逻辑出错。第二个细节找 j 的循环条件用的是nums[j] nums[i]同样也带等号。因为右侧段是降序的我们要找“大于 nums[i] 的最小值”从右往左遇到的第一个严格大于 nums[i] 的数就是目标。如果不带等号遇到相等元素时会跳过正确的 j导致交换错误。第三个细节反转的起始位置是i 1。当 i 为 -1 时也就是整个数组已经是降序时反转的是整个数组。C 里begin() 0没问题其他语言注意下标处理即可。我用 Python 再写一版因为很多同学刷题用的是 Pythondef next_permutation(nums: List[int]) - None: 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 版本需要注意List需要从typing导入或者在 LeetCode 环境中默认已经可用。反转部分我建议用双指针手写比nums[i1:] reversed(nums[i1:])更不容易在面试中被追问细节时卡壳。3.4 复杂度分析为什么这是最优解这个算法的时间复杂度是 O(n)。第一遍从右往左扫描找 i最坏情况下扫描整个数组第二遍从右往左扫描找 j最多也是 O(n)第三遍反转 i1 到末尾最坏情况下反转整个数组。三个循环是串行的总复杂度 O(n)。空间复杂度是 O(1)因为我们只用了几个临时变量没有借助额外数组。整个操作都是原地完成的这一点在面试中非常重要。面试官经常会追问“能不能不借助额外空间”这道题本身就是这个问题的答案。有些人可能会想到用暴力法先生成所有排列排序然后找当前排列的下一个。这种方法的时间复杂度是 O(n!)不说空间复杂度爆炸光是生成排列就是灾难。所以如果你在面试中提出暴力法大概率会被追问最优解直接说出这三步走才是正道。4. 常见错误与排查实录4.1 误区一把“下一个排列”当成“交换最后一个升序对”这是我见过最多的错误。比如数组[1,3,2]有人看到最后两个数是 3 和 2是降序就找不到可以交换的数然后直接返回。但其实正确答案是[2,1,3]。为什么从右往左找到的第一对升序对是[1,3]i 指向 1。找到右侧大于 1 的最小元素是 2交换后变成[2,3,1]反转右侧得到[2,1,3]。如果只盯着局部相邻元素很容易错过“位置 i 可以和右侧更远的元素交换”这一层。正确的观察方式是把数组看成两部分左侧前缀 右侧降序后缀。我们动的是左侧最后一个能变大的位置。4.2 误区二第二步找 j 时没利用“降序”这个性质写成了线性扫描有些实现会在 i 右侧线性扫描一遍找最小的大数这样也能得到正确答案时间复杂度不变但代码更繁琐也更易错。更简洁的写法是直接利用“右侧是降序”这一性质从右往左找第一个大于 nums[i] 的数。这里的关键在于找到 i 之后i 右侧也就是 i1 到末尾一定是降序的。为什么因为 i 是从右往左第一对升序对的左端点这意味着右端点右侧的所有元素都是递减的。这是一个严格的数学结论想明白之后写代码非常快。如果忘记了这一点从右往左找 j 时条件写成while (j i nums[j] nums[i])之类也是可以工作的但逻辑上不够优雅。我建议还是写成标准形式while (nums[j] nums[i]) j--;前提是 i 右侧降序所以 j 一定找得到。4.3 误区三反转部分写错边界反转的起始位置是 i1不是 i也不是 i2。我们只需要把 i 后面的那一整段反转因为位置 i 本身已经换成了正确的较大的数不需要动。如果写成从 i 开始反转会把刚换好的 nums[i] 也反转掉结果必然错误。另外当 i 为 -1 时反转起始位置是 0也就是整个数组。有些语言里nums.begin() i 1中的i 1是 0没问题但如果你用 Java 或 Python 时要特别注意下标计算。建议写完之后拿几个测试用例手动跑一遍尤其是降序数组[3,2,1]和单元素数组[1]。4.4 验证数组的方法手动走一遍测试用例面试或平时练习时我习惯准备几个固定测试用例每次改完代码都先跑一遍升序数组[1,2,3]下一个排列是[1,3,2]降序数组[3,2,1]下一个排列是[1,2,3]带重复的数组[1,1,5]下一个排列是[1,5,1]全相同数组[2,2,2]下一个排列是[2,2,2]长度 1 的数组[1]下一个排列是[1]中等复杂度[1,5,8,4,7,6,5,3,1]下一个排列是[1,5,8,5,1,3,4,6,7]用一个具体的数组完整手推一遍比自己盲目跑测试用例有用得多。因为手推能帮你确认每一步的 j、i 是否正确也能帮你理解为什么是“右侧降序”而不是“右侧乱序”。5. 举一反三这题还能延伸出哪些用法5.1 生成全排列的第 k 个排列LeetCode 第 60 题“排列序列”就是一个典型的延伸。要求给定 n 和 k返回 1 到 n 组成的第 k 个排列。最直观的做法是从最小的排列[1,2,...,n]开始连续调用 k-1 次“下一个排列”但这样时间复杂度是 O(k*n)不够优雅。更优的做法是利用阶乘分解来确定每一位的数但理解基于“下一个排列”的朴素方案仍然很有价值因为它能帮你直观感受“字典序排列的跳转顺序”。如果你能把“下一个排列”写得很熟面试时遇到“第 k 个排列”你可以先给出朴素方案再逐步优化到阶乘分解这是非常加分的答题路径。5.2 求当前排列的字典序排名另一个常见变式是给定一个排列求它在所有排列中按字典序排第几。这个问题的核心思路和“下一个排列”类似都是从左往右统计“固定前缀后后面还有多少种排列”。举个例子[2,3,1]的排名第一位是 2比 2 小的数有 1所以以 1 开头的排列有 2! 个排名至少加 2。第二位是 3剩余数是 [1,3]比 3 小的数有 1所以以 1 放在第二位的排列有 1! 个再加 1。最终排名是 4从 1 开始计数。这种“按位置统计贡献”的思路说到底还是字典序的底层逻辑。5.3 实际业务里的应用场景不要觉得排列算法只在面试里有用。我在做电商系统的推荐排序时遇到过一次需要给若干商品生成“下一个展示顺序”的需求候选商品集合固定每次展示顺序要按字典序递增切换以避免用户看到完全相同的排序。当时我直接想到了这道题的三步走把商品 ID 数组当成排列来处理每次点击“换一批”就调用一次“下一个排列”逻辑时间复杂度和空间占用都非常理想。还有一次是在做权限组合测试时需要枚举一组开关状态的所有组合状态。开关状态可以看作是 0/1 排列从全 0 到全 1 按字典序走一遍正好覆盖所有情况。很多迭代式枚举的场景本质上就是“下一个排列”的应用。刷题时多想想这些落地场景印象会深刻得多。5.4 C 标准库的启示顺带提一个有意思的事实C 标准库algorithm里有一个现成的函数叫next_permutation用法就是传入迭代器范围原地修改成下一个排列返回 bool 表示是否存在下一个排列。如果你用 C 刷题可以直接调库但面试时千万不要只调用库函数而不解释原理面试官要的是你理解背后的逻辑。了解了标准库实现之后你再回来看这道题会发现题目的解法其实就是标准库实现的核心逻辑。这也是为什么它能进 LeetCode 热题 100它不只是一个孤立题目而是许多算法与库函数的基石。6. 写在最后的一点个人经验刷这道题的时候我踩过最深的坑就是第二步找 j 时没有用等号导致在重复元素出现时交换错位置。后来养成了一个习惯凡是涉及“找严格大于/小于”的算法一律先写明条件里要不要带等号再动手写代码。这个习惯帮我避免了很多低级错误。还有一个小技巧刷完这道题之后建议你顺手把“上一个排列”也写一遍。方法是完全对称的从右往左找第一个 nums[i] nums[i1]然后找右侧小于 nums[i] 的最大数交换再把右侧反转。写一遍对称版本你对三步走的理解会从“背代码”变成“真懂”。如果你正准备面试拿这道题练手时不妨模拟真实面试环境先跟面试官讲清楚思路再在白板上写代码最后主动分析复杂度和边界情况。这套流程走下来你收获的不只是一道题而是解决一类排列问题的思维框架。