Next Permutation 是 LeetCode Hot 100 里面一道非常经典的数组题。
这道题第一次看时，很多人都会有一种“好像能理解题意，但不知道该怎么下手”的感觉。因为它不像普通的排序题，也不像常规的双指针题，它真正考察的是：
注意这里的关键词不是“随便找一个更大的排列”，而是：
-
必须比当前排列大
-
并且要是所有更大排列里最小的那个
这就说明我们不仅要让排列变大，而且还要尽量 只变大一点点。
你给出的这份 Java 代码，就是这道题最经典、最标准的写法。 它的核心思想可以概括成三步：
-
从右往左找到第一个“下降点”
-
从右往左找到刚好比它大的数进行交换
-
把后缀部分反转成升序
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给你一个整数数组 nums，要求你将它原地修改为它的 下一个排列。
所谓“下一个排列”，指的是：
在所有按字典序排序的排列中，当前排列后面的那个紧邻排列。
如果当前数组已经是最大的排列，那么就把它重排成最小的排列，也就是升序排列。
例如：
-
[1,2,3]的下一个排列是[1,3,2] -
[1,3,2]的下一个排列是[2,1,3] -
[3,2,1]已经是最大排列了，所以下一个排列是[1,2,3]
这道题要求 原地修改，也就是说不能额外创建一个大数组来存结果。
示例
示例 1
输入：nums = [1,2,3] 输出：[1,3,2]
因为 [1,2,3] 的所有排列按字典序排列后是：
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
所以它的下一个排列就是 [1,3,2]。
示例 2
输入：nums = [3,2,1] 输出：[1,2,3]
因为 [3,2,1] 已经是字典序最大的排列了，所以要回到最小排列。
示例 3
输入：nums = [1,1,5] 输出：[1,5,1]
因为在比 [1,1,5] 更大的排列里，最小的那个是 [1,5,1]。
这道题到底在问什么？
这道题真正的难点，不在代码本身，而在于“下一个排列”这个概念不够直观。
我们可以把数组看成一个数字串。
例如：
[1,2,3]
可以理解成数字 123。
它的下一个排列，其实就是所有由这几个数字组成的排列中，字典序紧跟在它后面的那个。
再比如：
[1,3,2]
它的下一个排列不是随便找一个更大的，而是：
[2,1,3]
因为这是所有比 132 更大的排列中，最小的那个。
所以问题本质上就是：
如何让当前排列变大，并且尽量只大一点点。
这就是整道题的核心。
最直接的想法为什么不行？
如果不考虑效率，一个最直接的方法是：
-
先把数组的所有排列全部生成出来
-
按字典序排序
-
找到当前排列的位置
-
取它后面的那个排列
这个思路当然可以得到答案，但效率极低。
因为长度为 n 的数组一共有：
n!
种排列。
当 n 稍微大一点时，这种做法就完全不现实了。
所以我们必须想办法直接在当前数组上做局部调整，快速得到“下一个排列”。
核心思路
这道题的标准解法其实只有三步，但每一步都很关键。
第一步：从右往左找到第一个下降的位置
我们从数组右侧开始往左看，找到第一个满足：
nums[i] < nums[i + 1]
的位置。
为什么找这个位置？
因为从右往左看，如果某一段一直是非递增的，比如：
5 4 3 2
那么这段后缀已经是当前情况下最大的排列方式了。 想让整个数组变得更大，就必须在更靠左的位置做改动。
所以我们要找的，其实就是：
最右边那个还能让整体变大的突破口。
这个位置通常叫做“拐点”或者“下降点”。
第二步：从右往左找到第一个比 nums[i] 大的数
找到下降点之后，我们知道：
-
nums[i]这个位置需要变大一点 -
但又不能变大太多
所以最合适的做法就是：
在右边后缀里，找一个刚好比 nums[i] 大的最小值。
由于右边这段后缀本身是非递增的，所以从右往左找，第一个比 nums[i] 大的数，就是我们要交换的对象。
然后把这两个数交换。
这样做完之后，整体排列一定变大了，而且变化尽量小。
第三步：把 i+1 之后的后缀反转
交换之后，后缀部分虽然还是由原来的那些数字组成，但它此时仍然是一个降序状态。
而为了让整个排列在“已经变大”的前提下尽量小，我们应该把后缀调整成最小的排列方式，也就是升序。
由于交换前后，这段后缀本身具有特殊结构，所以只需要直接反转，就能把它变成升序。
这一步非常关键，因为它保证了答案是：
恰好大一点，而不是大很多。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 1. 从右往左找到第一个下降点
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
// 2. 如果找到了下降点，就从右往左找到第一个比 nums[i] 大的数
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) j--;
swap(nums, i, j);
}
// 3. 反转下降点后面的部分，使其变成升序
reverse(nums, i + 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 = nums.length - 1;
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}
代码拆解
这段代码虽然不长，但逻辑非常精妙。 下面一步一步来看。
1. 为什么先从右往左找下降点？
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
这里的意思是：
从右往左，找到第一个满足：
nums[i] < nums[i + 1]
的位置。
为什么要这样找？
因为如果从右往左看，一段后缀始终满足：
nums[i] >= nums[i+1]
说明这段后缀是非递增的。
而非递增序列，在排列意义上已经是“最大后缀”了。 如果你只在这段后缀内部调整，是不可能得到更大的整体排列的。
所以必须找到更左边那个能发生变化的位置。
例如：
[1,2,7,4,3,1]
从右往左看：
-
4 >= 3 -
3 >= 1 -
7 >= 4
说明后缀 7,4,3,1 是非递增的。 直到看到：
2 < 7
这时 i = 1，也就是值为 2 的位置，它就是下降点。
2. 为什么要从右往左找第一个更大的数？
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) j--;
swap(nums, i, j);
找到下降点 i 之后，说明：
-
nums[i]需要换成一个更大的数 -
但为了让结果尽可能小，应该换成“刚刚好比它大一点”的那个数
右侧后缀本来就是非递增的，所以从右往左找时，第一个满足：
nums[j] > nums[i]
的数，就是最合适的交换对象。
为什么？
因为越靠右的更大元素，数值越小，越接近 nums[i]。 这样交换后，整体变化最小。
例如：
[1,2,7,4,3,1]
下降点是 2。 从右往左找第一个比 2 大的数，找到的是 3。 交换后变成：
[1,3,7,4,2,1]
这一步保证了整体变大，而且增幅尽量小。
3. 为什么最后要反转后缀？
reverse(nums, i + 1);
交换之后，后缀部分仍然是一个非递增序列。
但既然前面那一位已经变大了，那么为了让整体结果是“下一个”排列，后面的部分就必须尽量小。
而一个序列的最小排列方式就是升序。
由于原后缀是降序或非递增的，所以直接反转就能得到升序结果。
这一步是整道题最精华的地方。
例如刚才交换后的数组：
[1,3,7,4,2,1]
后缀部分是：
[7,4,2,1]
把它反转后得到：
[1,2,4,7]
整个数组就变成：
[1,3,1,2,4,7]
这就是原数组的下一个排列。
手动模拟一遍
我们用经典例子来走一遍：
nums = [1,2,3]
第一步：找下降点
从右往左：
-
2 < 3
所以下降点是 i = 1，值为 2。
第二步：找右边第一个更大的数
从右往左找第一个大于 2 的数，找到 3。
交换后变成：
[1,3,2]
第三步：反转后缀
此时 i + 1 = 2，后缀只有一个元素 [2]，反转后不变。
最终结果：
[1,3,2]
这就是答案。
再看一个最大排列的情况
再看：
nums = [3,2,1]
第一步：找下降点
从右往左检查：
-
2 >= 1 -
3 >= 2
一路都找不到满足 nums[i] < nums[i+1] 的位置。
这说明整个数组是完全非递增的，也就是它已经是最大的排列。
此时 i 会变成 -1。
第二步：由于 i < 0，不交换
第三步：直接反转整个数组
reverse(nums, 0)
结果变成：
[1,2,3]
也就是最小排列。
这正好符合题目要求。
为什么这个算法一定正确？
因为它严格遵循了“让排列刚好变大一点”的原则。
第一层：尽量从右边开始调整
因为越靠右的位置变化，对整体字典序影响越小。 所以我们从右往左找第一个可以变化的位置。
第二层：在该位置上只增加一点点
找到下降点后，不是随便换一个更大的数，而是找“刚好比它大的最小值”。
第三层：后缀改成最小排列
前面已经变大了，后面就必须尽量小，这样整体才是“紧邻”的下一个排列。
这三层逻辑结合起来，就保证了算法的正确性。
复杂度分析
时间复杂度
整个过程最多做三次线性扫描：
-
找下降点
-
找交换位置
-
反转后缀
所以总时间复杂度是：
O(n)
空间复杂度
只用了常数级额外变量，因此空间复杂度是：
O(1)
而且题目要求原地修改，这个解法也正好满足要求。
这道题真正想考什么？
这道题表面上像是排列题，但本质上它考察的是：
第一，能不能理解字典序变化的本质
不是简单让数组变大，而是：
让它变成刚好比当前大的那个排列。
这要求我们既要会“变大”，又要会“尽量少变”。
第二，能不能发现后缀的结构特征
从右往左找到下降点的过程，本质上是在利用：
数组右侧后缀一定处于某种最大排列状态。
正是这个结构，才让我们可以用“交换 + 反转”在线性时间内完成操作。
所以这道题其实非常锻炼思维转换能力。
和全排列有什么区别？
很多人看到“排列”这两个字，容易联想到“全排列”。
但这两题的目标完全不同。
全排列
是要生成所有可能的排列，通常用回溯。
下一个排列
是要在当前排列基础上，直接找到字典序紧邻的下一个排列。
所以这题不需要枚举所有排列，更不需要回溯。 它是一个非常典型的“数组规律题”。
总结
这道题的核心思路可以概括成一句话：
从右往左找到第一个可以让整体变大的位置，用右侧刚好更大的数和它交换，再把后缀调整成最小排列。
具体步骤就是：
-
从右往左找到第一个
nums[i] < nums[i+1]的位置 -
从右往左找到第一个
nums[j] > nums[i]的位置 -
交换
nums[i]和nums[j] -
反转
i+1之后的后缀
如果找不到这样的 i，说明当前已经是最大排列，直接反转整个数组即可。
这是一道非常经典、也非常值得反复理解的题。 因为它不仅仅是在考你会不会写代码，更重要的是在考你能不能看懂“字典序”和“局部最优调整”背后的规律。
把这道题真正吃透之后，再去看很多排列相关题目时，你会更容易抓住关键结构。
