31. 下一个排列（Next Permutation）
频次 ★★★ · 难度 🟡 · 高频：阿里
题目
给定一个整数数组，表示一个排列，原地修改为字典序中的下一个更大的排列。如果不存在更大的排列，则修改为最小的排列（升序）。
示例：
输入: [1, 2, 3]
输出: [1, 3, 2]
输入: [3, 2, 1]
输出: [1, 2, 3]
思路
三步法：
- 从右向左找第一个下降的位置
i（即nums[i] < nums[i+1]） - 从右向左找第一个大于
nums[i]的元素j，交换nums[i]和nums[j] - 翻转
i+1到末尾的部分（使其变为最小排列）
如果找不到下降位置，说明当前是最大排列，直接翻转整个数组。
例如 [1,3,5,4,2]：
- 找到 i=1（3<5）
- 找到 j=3（4 是从右第一个大于 3 的）
- 交换 →
[1,4,5,3,2] - 翻转后面 →
[1,4,2,3,5]
代码
public void nextPermutation(int[] nums) {
int n = nums.length;
// 1. 找第一个下降位置
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i >= 0) {
// 2. 找第一个大于 nums[i] 的元素并交换
int j = n - 1;
while (nums[j] <= nums[i]) j--;
swap(nums, i, j);
}
// 3. 翻转 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;
}
private void reverse(int[] nums, int start, int end) {
while (start < end) swap(nums, start++, end--);
}复杂度
- 时间：O(n) — 最多三次线性扫描
- 空间：O(1) — 原地操作
边界条件
- 数组已是最大排列（降序，如
[3,2,1]）：第一步找不到下降位置（i最终为 -1），跳过交换步骤，直接翻转整个数组得到最小排列[1,2,3]。 - 数组只有一个元素：
i = n - 2 = -1，同样跳过交换，翻转”整个数组”（其实只有一个元素，翻转无影响）。 - 数组已是最小排列（升序）：正常走三步得到字典序中紧邻的下一个排列。
变式
- 求上一个排列（Previous Permutation）：思路完全对称——从右向左找第一个”上升”的位置，再从右向左找第一个小于它的元素交换，最后把后面部分翻转成降序（而不是升序）。
- 求排列的字典序中第 k 个排列（LeetCode 60 题）：用康托展开的思路，通过阶乘进制直接计算每一位，而不是重复调用”下一个排列” k 次（否则 k 很大时效率太低）。
易错点
- 第 2 步”从右向左找第一个大于
nums[i]的元素”，不能写成”找到第一个大于就停”从左往右找——因为i+1到末尾这一段是降序的，从右往左找到的第一个大于nums[i]的元素，才是”大于 nums[i] 的元素里最小的那个”，这样交换后能保证是紧邻的下一个排列而不是跳过了中间的排列。 - 第 3 步的翻转不能省略：只交换不翻转，
i+1之后依然是降序，不是字典序最小的排列，导致得到的不是”紧邻的下一个”而是一个更大的排列。
面试追问
- 为什么第 2 步一定能找到满足条件的元素？ 因为第 1 步保证了
nums[i] < nums[i+1]，而i+1到末尾是降序的，所以nums[i+1]本身就满足”大于nums[i]”，第 2 步的while循环最坏情况下也会在j = i+1处停下，不会出现找不到的情况。 - 能不能证明”交换 + 翻转”两步能得到字典序里紧邻的下一个排列，而不是跳过或重复？ 交换让第
i位变成”比原值大的最小候选”，是局部意义上最小的增量；翻转把i之后变成升序（该区间内字典序最小的排列），两者结合保证了整体是”比原排列大的所有排列中最小的一个”，也就是紧邻的下一个。