企业官网建设流程全解析

我最早刷到这道“下一个排列”的时候，其实是在面试前突击准备算法题。当时第一眼看到题目描述，觉得挺简单：不就是找一个比当前排列大一点的排列吗？结果动笔一写才发现，这题本质上考的是对字典序的理解、对数组规律的观察，以及“如何在不引入额外空间的情况下完成一次精准的调整”。它不止频繁出现在 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.length，1 <= n <= 100，0 <= 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[i+1]的相邻位置。在这个例子中，站在 i = 3（也就是数字 4）这里，nums[3]=4，nums[4]=7，4 < 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[i+1]的位置 i。如果找不到，说明整个数组是降序排列，已经是字典序最大的排列，直接把整个数组反转成升序返回。

第二步，在 i 右侧，从右往左扫描，找到第一个比 nums[i] 大的数 nums[j]（因为右侧是降序，所以从右往左第一个大于 nums[i] 的数，必然就是大于 nums[i] 的最小值）。交换 nums[i] 和 nums[j]。

第三步，把 i+1 到数组末尾这一段整体反转，因为这段当前是降序，反转后变成升序，得到字典序最小的状态。

这三步缺一不可。只做第一步和第二步，右侧的降序段会让整个排列不是最小的大排列；只做第一步和第三步，位置 i 没有变大，排列甚至可能变小；只做第二步不选最小的比 nums[i] 大的数，增长幅度就不是最小。

这套思路的本质是“字典序下一个状态的生成”。想通之后，你会发现它与递归全排列里的“剪枝”“回溯”有奇妙的一致性：回溯法生成全排列时，就是在每一个前缀固定后，让后缀从小到大排列；而“下一个排列”就是找到最后一个还能增大的前缀位置，然后重组后缀。

3. 实现细节：写出优雅且不易出错的代码

3.1 边界情况一：数组长度只有 1

长度为 1 时，[x]的字典序中既没有比它大的排列，也没有比它小的排列，下一个排列就是它自己。用三步走来看：从右往左扫描，根本找不到nums[i] < nums[i+1]，因为只有一个元素，循环进不去。此时按照规则应该反转整个数组，反转后还是自己，所以直接返回即可，不需要特判。

不过很多标准答案里会单独写一个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[i+1]，因为全是相等，所以直接反转。反转后还是[2,2,2]，这个结果是正确的，因为所有排列都相同，下一个排列就是它自己。

3.3 代码实现：以第一个大于 nums[i] 的数作为关键

我用类 C 的伪代码写一遍核心逻辑，方便大家直接对照：

void nextPermutation(vector<int>& 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[i+1]，这里一定要带等号。如果数组右侧存在相等元素，比如[1,2,2,3]，从右往左扫描：3 > 2，不满足；2 和 2 相等，满足>=，继续左移；2 和 1 比较，1 < 2，停下。这时 i 指向 1，这是正确的。如果你不小心写成了num[i] > nums[i+1]，相等的情况会被当成候选 i，导致后续逻辑出错。

第二个细节，找 j 的循环条件用的是nums[j] <= nums[i]，同样也带等号。因为右侧段是降序的，我们要找“大于 nums[i] 的最小值”，从右往左遇到的第一个严格大于 nums[i] 的数就是目标。如果不带等号，遇到相等元素时会跳过正确的 j，导致交换错误。

第三个细节，反转的起始位置是i + 1。当 i 为 -1 时，也就是整个数组已经是降序时，反转的是整个数组。C++ 里begin() + 0没问题，其他语言注意下标处理即可。

我用 Python 再写一版，因为很多同学刷题用的是 Python：

def 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 -= 1

Python 版本需要注意List需要从typing导入，或者在 LeetCode 环境中默认已经可用。反转部分我建议用双指针手写，比nums[i+1:] = reversed(nums[i+1:])更不容易在面试中被追问细节时卡壳。

3.4 复杂度分析：为什么这是最优解

这个算法的时间复杂度是 O(n)。第一遍从右往左扫描找 i，最坏情况下扫描整个数组；第二遍从右往左扫描找 j，最多也是 O(n)；第三遍反转 i+1 到末尾，最坏情况下反转整个数组。三个循环是串行的，总复杂度 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 右侧（也就是 i+1 到末尾）一定是降序的。为什么？因为 i 是从右往左第一对升序对的左端点，这意味着右端点右侧的所有元素都是递减的。这是一个严格的数学结论，想明白之后写代码非常快。

如果忘记了这一点，从右往左找 j 时条件写成while (j > i && nums[j] < nums[i])之类，也是可以工作的，但逻辑上不够优雅。我建议还是写成标准形式：while (nums[j] <= nums[i]) j--;，前提是 i 右侧降序，所以 j 一定找得到。

4.3 误区三：反转部分写错边界

反转的起始位置是 i+1，不是 i，也不是 i+2。我们只需要把 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[i+1]，然后找右侧小于 nums[i] 的最大数交换，再把右侧反转。写一遍对称版本，你对三步走的理解会从“背代码”变成“真懂”。

如果你正准备面试，拿这道题练手时，不妨模拟真实面试环境：先跟面试官讲清楚思路，再在白板上写代码，最后主动分析复杂度和边界情况。这套流程走下来，你收获的不只是一道题，而是解决一类排列问题的思维框架。