#31
中等
中频
迭代法下一个排列
这是一道围绕数组展开的高频练习。建议先掌握「迭代法」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
题目分析
给你一个整数数组，它表示某个排列。
要求你原地把这个排列改成“按字典序紧挨着的下一个更大排列”。如果当前已经是最大的排列，就把它改成最小排列。
一句话概括：
在保持改动尽量小的前提下，把当前排列变成下一个更大的排列。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：从右往左找第一个升序断点，和右侧刚好更大的数交换，再把后缀反转成最小序。
推荐代码
推荐解法：迭代法
时间复杂度： O(n)
空间复杂度： O(1)
核心思路： 从右往左找第一个升序断点，和右侧刚好更大的数交换，再把后缀反转成最小序。
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 从右向左找到第一个降序点
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
// 从右向左找到第一个大于 nums[i] 的元素
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
// 交换元素
swap(nums, i, j);
}
// 反转后续部分
reverse(nums, i + 1);
}
// 交换数组中的两个元素
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// 反转数组从 start 到末尾的元素
private void reverse(int[] nums, int start) {
int end = nums.length - 1;
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}结构化讲解
面试时怎么讲
开场思路
这题我会从右往左找“第一个还能变大”的位置，再做最小幅度调整。
核心过程
- 先从右往左找到第一个下降断点。
- 再在右侧找刚好比它大的数进行交换。
- 交换后把后缀反转成最小升序。
- 如果不存在断点，说明当前已经是最大排列，直接整体反转即可。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(1)。
面试补一句：这题最难的是理解为什么一定要“从右往左找断点”。
核心思路
下一个排列的关键是“在尽量靠右的位置做最小增量”。先找到可以变大的位置，再把它后面的部分整理成最小升序，就得到紧邻的下一个排列。
步骤讲解
1
从右往左找第一个下降断点
找到第一个满足 nums[i] < nums[i + 1] 的位置 i，它就是还能变大的地方。
为什么这样做：越靠右调整，整体变化越小，才是“下一个”排列。
对应代码提示：while (i >= 0 && nums[i] >= nums[i + 1]) i--;
2
找右侧刚好更大的数交换
从右往左找到第一个大于 nums[i] 的元素，与它交换。
为什么这样做：要让增量尽可能小，所以要选右侧最小的可行更大值。
对应代码提示：swap(nums, i, j);
3
把后缀反转成最小序
交换后，把 i + 1 之后的后缀反转成升序。
为什么这样做：前缀已经刚好变大，后缀必须尽可能小，才能得到紧邻下一个排列。
对应代码提示：reverse(nums, i + 1, nums.length - 1);
易错点
找断点方向写反
如果不是从右往左找，得到的变化不会是最小增量。
正确理解：必须从数组尾部往前扫描。
交换后直接结束
后缀仍然是降序，结果不会是最小的更大排列。
正确理解：交换之后一定还要反转后缀。
全降序数组没特殊处理
像 3 2 1 没有断点，下一排列应该回到最小升序。
正确理解：找不到断点时直接整体反转。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(1)
比其他方案更好在哪里：比生成所有排列再排序高效得多，是真正的原地线性做法。
适用判断：题目要求“字典序下一个/上一个排列”时，优先考虑断点 + 后缀处理。
额外提醒
- 断点尽量靠右，后缀尽量最小，是两个核心原则。
动画演示
如果你还没完全看懂，可以展开动画演示。
迭代法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
迭代法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入数组值（用逗号分隔），然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。