力扣热题100实战 | 第31期：下一个排列——数组规律的极致探索

力扣热题100实战 | 第31期：下一个排列——数组规律的极致探索

• • 前言
  • 一、题目：找下一个更大的排列
  • • 关键点解读
  • 二、第一反应：暴力枚举（理论上可行，实际上不可行）
  • • 核心思想
    • 复杂度分析
    • 为什么不可行？
  • 三、核心解法：经典三步走算法
  • • 3.1 规律发现
    • 3.2 算法步骤
    • 3.3 图解流程
  • 四、代码实现：三步走算法（面试终极答案）
  • • 代码解析
    • 复杂度分析
  • 五、细节剖析：面试官真正关心的问题
  • • Q1：为什么找下降点时要比较 `nums[i] >= nums[i+1]` 而不是 `>`？
    • Q2：为什么找交换点时要从右向左找第一个大于 `nums[i]` 的数？
    • Q3：如果数组是 `[3,2,1]` 这种完全降序，算法怎么处理？
    • Q4：为什么交换后要反转 `i+1` 到末尾？
    • Q5：这个算法能处理重复元素吗？
  • 六、面试官追问进阶版
  • • 追问1：如何实现上一个排列？
    • 追问2：如何实现第k个排列（LeetCode 60）？
    • 追问3：如果要求返回所有排列，怎么实现？
    • 追问4：如何验证当前排列是否是最大排列？
  • 七、实际开发：这道题到底有什么用？
  • • 场景1：字典序迭代器
    • 场景2：密码破解中的穷举
    • 场景3：数字游戏中的“下一关”
    • 场景4：排列组合的数学问题
    • 场景5：面试中的思维题
  • 八、总结：从一道题到一类题
  • 附录：思考题

在有序的世界里寻找下一个更大的排列，就像在数字的迷宫中寻找唯一正确的出口。这道题教会我们：当数字序列达到峰值时，如何通过最小的调整，让它重新焕发更大的生机。

前言

你好，我是@礼拜天没时间。

上一期我们攻克了“串联所有单词的子串”（第30题），掌握了滑动窗口在单词级别匹配中的应用。这一期，我们来解一道非常有意思的题目——下一个排列（LeetCode 第31题）。

这道题在力扣上被标记为“中等”，但它的难度并不在于代码实现有多复杂，而在于发现规律的过程。很多同学第一次看到这道题时，要么完全不知道从何下手，要么虽然能写出代码但讲不清楚为什么这样写。

今天，我希望能带你从最朴素的“手工找下一个排列”出发，一步步推导出那个优雅的三步算法，并理解它背后的数学原理。

一、题目：找下一个更大的排列

先看题目描述（LeetCode 第31题）：

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列 。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间 。

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]
解释：所有排列按字典序排序为：[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]
[1,2,3] 的下一个更大排列是 [1,3,2]

示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]
解释：[3,2,1] 已经是最大排列，没有下一个更大排列，所以返回最小排列 [1,2,3]

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

关键点解读

二、第一反应：暴力枚举（理论上可行，实际上不可行）

当我第一次看到这道题，我的第一反应和第46题“全排列”一样：生成所有排列，排序，然后找到当前排列的下一个 。

核心思想

复杂度分析

• 时间复杂度：O(n!) —— 生成所有排列是指数级复杂度
• 空间复杂度：O(n!) —— 需要存储所有排列

为什么不可行？

三、核心解法：经典三步走算法

3.1 规律发现

观察一个例子：[1,2,3,5,4,2]

我们希望找到下一个更大的排列。直觉上，我们希望变动尽量靠右的位置，因为越靠右变动，对整个数字的影响越小 。

让我们从右向左看：

• 最后两位 [4,2] 是降序，无法通过交换这两位得到更大的数
• 再看 [5,4,2] 也是降序
• 再看 [3,5,4,2] —— 这里 3 后面是降序，而且 3 < 5

这个 3 就是我们要找的下降点 。因为从它往右都是降序，说明这一部分已经是最大排列，无法通过只改动右边得到更大的排列。

3.2 算法步骤

第一步：找下降点 从右向左遍历，找到第一个满足 nums[i] < nums[i+1] 的位置 i 。这个 i 就是我们要调整的“小数”位置。

第二步：找交换点 如果找到了 i，再从右向左遍历，找到第一个大于 nums[i] 的数 nums[j] 。这个 j 就是我们要交换的“大数”位置。

第三步：交换并反转

• 交换 nums[i] 和 nums[j]
• 将 i+1 到末尾的部分反转（因为原来这部分是降序，反转后变成升序，即最小排列）

特殊情况：如果第一步没找到下降点，说明整个数组是降序排列，已经是最大排列，直接反转整个数组 。

3.3 图解流程

以 nums = [1,2,3,5,4,2] 为例：

第1步：找下降点

[1, 2, 3, 5, 4, 2]
↑ ↑
4 > 2? 是，继续
↑ ↑
5 > 4? 是，继续
↑ ↑
3 > 5? 否！找到了下降点 i = 2 (值为3)

第2步：找交换点 从右向左找第一个大于3的数：

[1, 2, 3, 5, 4, 2]
↑ 2 < 3? 是，跳过
↑ 4 > 3? 是！找到了 j = 4 (值为4)

第3步：交换 交换 nums[2] 和 nums[4]：

交换前：[1, 2, 3, 5, 4, 2]
交换后：[1, 2, 4, 5, 3, 2]

第4步：反转 i+1 到末尾 原来 i+1=3 到末尾是 [5,3,2]，反转后为 [2,3,5]：

最终结果：[1, 2, 4, 2, 3, 5]

验证：123542 的下一个确实是 124235 ✅

四、代码实现：三步走算法（面试终极答案）

class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
if (n <= 1) return; // 长度小于等于1，直接返回

// 1. 从右向左找第一个下降点 i
int i = n – 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i—;
}

// 2. 如果找到了下降点
if (i >= 0) {
// 从右向左找第一个大于 nums[i] 的数 j
int j = n – 1;
while (j >= 0 && nums[j] <= nums[i]) {
j—;
}
// 交换 i 和 j
swap(nums, i, j);
}

// 3. 反转 i+1 到末尾（如果是降序排列，i 会是 -1，这里反转整个数组）
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;
}

// 反转数组从 start 到 end 的部分
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end—;
}
}
}

代码解析

复杂度分析

• 时间复杂度：O(n) —— 最多遍历数组三次
• 空间复杂度：O(1) —— 只用了常数个变量

五、细节剖析：面试官真正关心的问题

Q1：为什么找下降点时要比较 nums[i] >= nums[i+1] 而不是 >？

答案：因为要跳过所有非严格递增的情况。如果遇到相等的情况，也不能作为下降点，因为交换相等的数不会让排列变大。例如 [1,2,2,3]，如果错误地把第一个2当作下降点，交换后会得到更小的排列 。

Q2：为什么找交换点时要从右向左找第一个大于 nums[i] 的数？

答案：因为 [i+1, end] 是降序排列，所以从右向左第一个大于 nums[i] 的数，就是所有大于 nums[i] 的数中最小的那个 。这保证了交换后，新排列的增幅尽可能小。

Q3：如果数组是 [3,2,1] 这种完全降序，算法怎么处理？

答案：

• 第一步找下降点：i 最终会变成 -1
• 第二步 if (i >= 0) 不执行
• 第三步反转：reverse(nums, 0, n-1) 将整个数组反转，得到 [1,2,3]

Q4：为什么交换后要反转 i+1 到末尾？

答案：交换后，[i+1, end] 这部分仍然是降序（因为原来就是降序，而且换进来的数比原来的 nums[i] 大，不会破坏降序性质）。降序是这部分的最大排列，我们需要的是最小排列，所以反转成升序 。

Q5：这个算法能处理重复元素吗？

答案：能。关键在于比较时用了 >= 和 <=，跳过了相等的情况，确保找到的下降点是严格下降，找到的交换点是严格大于 。

六、面试官追问进阶版

追问1：如何实现上一个排列？

思路：对称操作即可

• 找第一个上升点（nums[i] > nums[i+1]）
• 找第一个小于它的数
• 交换并反转

追问2：如何实现第k个排列（LeetCode 60）？

思路：用阶乘数系统（Factorial Number System），通过数学计算直接定位，不需要逐个生成 。

追问3：如果要求返回所有排列，怎么实现？

思路：用回溯算法，每次找到下一个排列并记录，直到回到最小排列 。

public List<List<Integer>> getAllPermutations(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// 先排序得到最小排列
Arrays.sort(nums);
do {
result.add(arrayToList(nums));
nextPermutation(nums);
} while (!isSortedDesc(nums)); // 直到变成最大排列
return result;
}

追问4：如何验证当前排列是否是最大排列？

思路：检查是否整个数组是降序。即遍历一次，看是否有 nums[i] < nums[i+1] 。

七、实际开发：这道题到底有什么用？

很多读者会问：“下一个排列，实际工作中哪用得到？”

其实它的思想无处不在：

场景1：字典序迭代器

在生成组合、排列的算法中，经常需要按字典序迭代所有可能。这个算法就是迭代器的核心 。

场景2：密码破解中的穷举

在暴力破解密码时，需要按字典序生成所有可能的字符组合，这个算法可以高效实现。

场景3：数字游戏中的“下一关”

在有些数字游戏中，需要找到比当前数字大的下一个数字，比如“找出大于给定数的最小回文数”。

场景4：排列组合的数学问题

在数学竞赛或算法竞赛中，经常需要处理排列的顺序问题，这道题是基础。

场景5：面试中的思维题

这道题考察的是发现规律的能力，而不是死记硬背算法，所以经常作为面试题出现 。

八、总结：从一道题到一类题

回顾一下，我们从下一个排列学到了什么：

力扣热题100的第三十一题，不是为了难住你，而是为了告诉你：有些问题看似复杂，但当你找到了规律，就能写出简洁而优雅的代码。这种发现规律的能力，比死记硬背一百道题都重要。

下一期预告：《最长有效括号》——栈与动态规划的巅峰对决

附录：思考题

看完这篇文章，你可以试着回答：

欢迎在评论区留下你的思考！