Hot 100 --- 下一个排列

本文概览：本文讲解下一个排列：要让排列"只变大一点点"，就得找从右往左第一个升序相邻对（它右边的降序段已经顶到头了），用降序段里比它大的最小数替换，再把右边那段反转成升序，让它变成新前缀下的最小排列

一、题目

二、题目分析

1. 题目要求

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。例如arr = [1, 2, 3]，以下这些都可以视作它的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]等。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即元素按升序排列）。

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

示例 1：nums = [1, 2, 3]→[1, 3, 2]

示例 2：nums = [3, 2, 1]→[1, 2, 3]

示例 3：nums = [1, 1, 5]→[1, 5, 1]

2. 怎么想这题？

先搞清楚"排列的大小"怎么比。字典序是从左往右逐位比，第一个不一样的位置谁大，谁就更大。比如[1,2,3]和[1,3,2]：第一位都是 1，第二位 2 < 3，所以[1,3,2]更大。

再想"下一个"到底意味着什么。把[1,2,3]的所有排列按字典序排成一列：

123, 132, 213, 231, 312, 321

123的下一个就是132。注意它并不是"随便找一个更大的"——比123大的排列有好几个，但排在123后面紧挨着的只有132。所以"下一个排列"要同时满足两件事：得比当前这个大，而且要大得尽可能少。

那怎么才能"只升一级"？从字典序的比较规则往下推：

• 两个排列谁大，取决于最靠左的那个不同位。所以想让[1,2,3]往前走一小步，改动的位置越靠右越好——改个位只挪一小步，改首位就直接跳到另一大批排列去了。要改，就改最靠右的那个"能改的位置"。
• 改完之后，剩下那几位还得排成它们最小的顺序。不然中间会隔着别的排列，得到的就不是"下一个"，而是"下几个"。

哪一位才是"能改的位置"？从右往左看后缀。从最右边开始往左扫，如果发现某一段是严格降序的（一路递减），那这一段本身就已经是"这几个数能组成的最大排列"了——降序是最大的顺序，在它内部无论怎么重排都只会变小，靠它没法让整个排列变大。

那就继续往左退，直到第一次出现nums[i] < nums[i+1]：这一位比它右边那位小，说明"这一段还没顶到头"，把它换大一点，整个排列就能变大。而且因为是从右往左遇到的第一个，它就是那个"能改的最靠右的位置"——动它，新排列离当前最近。

所以这个位置（降序段左边第一个升序相邻对）就是"能升一级"的入口。

换成谁、换完还要做什么？这两步决定了答案到底是"下一个"还是"下几个"：换进来的数得比nums[i]大，否则排列没变大；但又要"大得尽量少"，挑得太大就等于跳级。换完之后，i后面那几位还是降序（也就是它们能组成的最大排列），而我们要的既然是"下一个"，后面就应该取最小的排列。

3. 需要解决哪几个问题？

问题一：为什么"能改的位置"一定是从右往左第一个升序相邻对？比它更靠右的位置为什么动不了？

问题二：换成哪一个数，才算"只升一级"而不跳级？这个数藏在哪，怎么快速找到它？

问题三：交换完就结束了吗？i后面那一段该怎么处理，才能让它成为最小排列？

问题四：如果从头扫到尾都没找到这个位置（比如[3,2,1]），说明什么？该怎么收尾？

三、思路概览

publicvoidnextPermutation(int[]nums){intn=nums.length;inti=n-2;// 从右往左，找到第一个升序相邻对 nums[i] < nums[i+1]while(i>=0&&nums[i]>=nums[i+1]){i--;}// 找到了就和右边"比它大的最小数"交换if(i>=0){intj=n-1;while(j>=0&&nums[j]<=nums[i]){j--;}inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}// 把 i 后面的降序段反转成升序（i = -1 时正好反转整个数组）intleft=i+1;intright=n-1;while(left<right){inttemp=nums[left];nums[left]=nums[right];nums[right]=temp;left++;right--;}}

思路简要说明：

1. 找交界点i：从右往左扫，第一个满足nums[i] < nums[i+1]的位置
2. 找替换对象j：在i右边从右往左扫，第一个比nums[i]大的位置
3. 交换nums[i]和nums[j]
4. 反转i+1到末尾，把降序变升序
5. 时间复杂度 O(n)，空间 O(1)

四、思路详解

先定标准：一次交换要满足什么，才算"升一级"而不是"跳级"？

题目要的是字典序里紧挨着的下一个，所以改动必须同时满足两条：

• 改的位置尽量靠右。两个排列谁大，由最靠左的不同位决定；改得越靠右，新排列和原排列挨得越近。
• 改完之后，后面那几位排成最小顺序。否则新排列后面还会跟着一串比它小的排列，中间隔着东西，那就不是"紧接着的下一个"了。

把这两条套到具体操作上，就得到三个动作：先找到最靠右的那个"能改的位置"，再把这一位换成"刚好大一点"的数，最后把后面那一段收拾成最小的顺序。下面逐个说明。

第一步：解决问题一——哪个位置才能改？

从右往左扫相邻两格nums[k]和nums[k+1]：

• 只要nums[k] >= nums[k+1]，就说明从k往右这一段是降序的。降序段已经顶到了它自己的最大排列，在它内部重新排列只会变小，不可能让整个数组变大，所以继续往左找。
• 一直往左，直到第一次遇到nums[i] < nums[i+1]。

这个i就是能变大的最靠右的位置，它把数组切成了两半：

[ ... 有潜力变大的部分 ... | i ] [ i+1 ... n-1 已经顶到头的降序段 ]

注意是"从右往左第一个"，这正好同时满足了上面那两条标准里的第一条：比i更靠右的位置全在降序段里，动它们只会让排列变小，压根不是"能改的位置"；而如果放着i不改编去动更靠左的位，改动幅度就大了，那就不是"下一个"而是"下很多个"了。比如[1,2,3,5,4]，从右往左第一个满足升序的是3 < 5（下标 2），改动这里就够了；要是去动前面的2，得到的就是[1,3,...]开头，早就跳过了一大批排列。

第二步：解决问题二——和谁交换？

现在要把nums[i]换成一个比它大的数，让排列变大。同时要"变大得最少"，所以还得满足：换进来的这个数，得是比nums[i]大的那些数里最小的一个。

那么去哪找？只能去i右边那段里找。左边那部分不能动（动了位置更靠左、变化更大），而且i左边是"降序段的终点"之上的部分，它右边的才是有序可查的降序段。

i右边nums[i+1 .. n-1]是降序的。在降序序列里从右往左扫，遇到的第一个大于nums[i]的数，就是"比它大的最小的那个"——因为越往左越大，从右往左数的第一个就是最小的大于它的数。

举个直观的例子：[1, 2, 3, 5, 4]里nums[i] = 3，右边降序段是5, 4。比 3 大的有 5 和 4，4 更小，所以换 4：

换 5 → [1, 2, 5, 3, 4] ← 跳得太远了，把"4 开头"的排列全跳过了 换 4 → [1, 2, 4, 5, 3] ← 只大一点点，这才是"下一个"

所以挑 4 不挑 5：换 5 相当于一步跨过了中间一大批排列。

第三步：解决问题三——交换完为什么还要反转？

交换之后，nums[i]变成了一个更大的值（3变成4），前缀[1, 2, 4]从此定下来。但接下来的目标是：在所有以[1, 2, 4]开头的排列里，取最小的那一个。

可刚刚换完的数组是[1, 2, 4, 5, 3]，它后面那一段5, 3仍然是降序的。降序意味着最大——也就是说[1,2,4,5,3]是"124开头"里最大的那个排列，而我们要的恰恰是"124开头"里最小的那个。

所以要把i后面这一段从降序反转成升序。降序 → 升序，正好是从最大变成最小：

[1, 2, 4, 5, 3] 反转后面两位 [1, 2, 4, 3, 5] ~~~~~ → ~~~~~ 降序(最大) 升序(最小)

这样得到的[1, 2, 4, 3, 5]才是"124开头"里最小的排列，也就是真正的"下一个"。

为什么反转（O(n)）就够了，不用排序？因为换完之后，i右边这一段本来就已经是降序的（降序序列里抽掉一个元素，剩下部分仍然降序），而降序反转过来就是升序——升序即最小。所以一次反转到位，不需要付出排序的代价。

第四步：解决问题四——整个数组降序怎么办？

如果第一步一路从右扫到最左边都没找到nums[i] < nums[i+1]（循环结束后i = -1），说明整个数组都是降序的，比如[3, 2, 1]。它已经是最大的排列，按题目要求"不存在下一个更大的排列时，重排为字典序最小的排列"，也就是要变成升序[1, 2, 3]。

处理办法很简单：跳过交换那一步，直接反转整个数组。代码里left = i + 1 = 0，反转范围正好是0到n-1的整个数组——同一个反转逻辑，顺手把特例也覆盖了，不用单独写分支。

五、完整执行过程

示例 1 的加强版：nums = [1, 2, 3, 5, 4]→[1, 2, 4, 3, 5]

初始: [1, 2, 3, 5, 4] ① 从右往左找第一个升序相邻对： i=3: nums[3]=5 >= nums[4]=4 → i=2 i=2: nums[2]=3 < nums[3]=5 → 停下，i = 2 ② 从右往左找第一个比 nums[2]=3 大的： j=4: nums[4]=4 <= 3 ? 否 → 停下，j = 4 ③ 交换 nums[2] 和 nums[4]： [1, 2, 4, 5, 3] ④ 反转 i+1=3 到 4： [1, 2, 4, 3, 5] 结果: [1, 2, 4, 3, 5] ✓

示例 2：nums = [3, 2, 1]→[1, 2, 3]（整体降序）

初始: [3, 2, 1] ① 从右往左找升序相邻对： i=1: nums[1]=2 >= nums[2]=1 → i=0 i=0: nums[0]=3 >= nums[1]=2 → i=-1 i < 0，说明整体降序，跳过交换 ② 反转 i+1=0 到 2（整个数组）： [1, 2, 3] 结果: [1, 2, 3] ✓

示例 3：nums = [1, 1, 5]→[1, 5, 1]（有重复元素）

初始: [1, 1, 5] ① i=1: nums[1]=1 >= nums[2]=5 ? 否 → 停下，i = 1 ② j=2: nums[2]=5 <= nums[1]=1 ? 否 → 停下，j = 2 ③ 交换 → [1, 5, 1] ④ 反转 i+1=2 到 2（只有一个元素，不用动） 结果: [1, 5, 1] ✓

六、代码细节

nums[i] >= nums[i+1]里为什么用>=（而不是>）？

这决定了重复元素下的正确性。[1, 1, 5]里nums[1]和nums[2]不相等还好说，但像[1, 1]这种，如果用>，第一步就会在nums[0] = nums[1]那里停下、把i定在 0；可[1, 1]本身并没有下一个更大的排列。用>=才会继续往左扫，最后正确地判定为"整体降序"，反转回[1, 1]。相等也算降序，因为交换两个相等的数并不会让排列变大。

nums[j] <= nums[i]里为什么用<=？

要的是严格大于nums[i]的数，所以扫描时跳过所有"小于等于"的。

i < 0时为什么不会出错？

交换那一段被if (i >= 0)兜住了；反转那一段left = i + 1 = 0，正好反转整个数组，刚好就是"整体降序要变成升序"的答案。

为什么不用直接排序？

排序要 O(n log n)，而且题目要求原地、常数空间。这里用"找i→ 找j→ 交换 → 反转"四步，每步都是线性的，整体 O(n)，比排序快，也更贴合排列本身的结构。

七、复杂度分析

时间复杂度 O(n)：三次线性扫描——找i一次、找j一次、反转一次，都是往左或往右单方向推进。

空间复杂度 O(1)：只用几个下标变量，交换和反转都在原数组上进行。

八、总结

这道题看起来绕，其实整套推导就建立在两个观察上：

观察一：降序段已经"顶到头"了。
一个降序的片段，它自己就是那一堆元素能组成的最大排列，在它内部怎么折腾都只会变小。所以真正能"变大"的位置，只能往左找，直到遇到第一个nums[i] < nums[i+1]的升序相邻对——这个交界点就是可改动的最靠右位置。

观察二：要"下一个"，就得变大幅度最小。

• 位置最小：i选从右往左第一个能变大的位置；
• 幅度最小：在右边降序段里挑"比nums[i]大的最小数"来换（降序段从右往左第一个大于它的就是它）；
• 收尾最小：换完后i后面还是降序（最大），反转成升序（最小），让它成为新前缀下的最小排列。

整段流程可以浓缩成一句话：从右往左找交界的i，在它右边找刚好大一点的那个数换上去，再把后面反转成升序。如果连i都找不到，说明本来就是最大排列，整个反转回去当最小排列即可。