- 2.23
- 找前面那个较小的数。
- 找后面那个刚好大一点的数。
- 交换它俩。
- 翻转剩下的尾巴。
- 第一次找转折点时，从-2 开始，因为有与 i+1 的对比，避免越界
- 只有当 index 不为-1 时才开始交换转折点
- 最后不管怎样，都反转转折点+1 后的数组
class Solution {
public void nextPermutation(int[] nums) {
int i=nums.length-2;
int temp=-1;
int tempIndex=-1;
while(i>=0){
if(nums[i]<nums[i+1]){
temp = nums[i];
tempIndex = i;
break;
}
i--;
}
if(tempIndex!=-1){
i = nums.length-1;
while(i>=0){
if(nums[i]>temp){
swap(nums,i,tempIndex);
break;
}else{
i--;
}
}
}
reverse(nums,tempIndex+1,nums.length-1);
}
public void swap(int[] nums,int l,int r){
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
public void reverse(int[] nums,int start,int end){
while(start<end){
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}核心逻辑（三步走策略）
为了找到“刚好大一点”的数，我们需要尽量改动靠右边的低位数字：
-
从后往前找“转折点”： 找到第一对相邻元素，满足
nums[i] < nums[i+1]。此时，i位置就是我们需要变大的地方。 -
找个稍微大点的数来替它： 在
i往后的数字里，找一个比nums[i]大、但又是其中最小的数，把它俩交换。 -
让后面变最小： 交换后，
i后面的部分还是降序的，为了让整体数值最小，我们需要把i之后的部分反转（变成升序）。
举个栗子：[1, 5, 8, 4, 7, 6, 5, 3, 1]
-
找转折点： 从后往前看，
4比7小，所以 4 是转折点。 -
找替身： 在
4后面的[7, 6, 5, 3, 1]中，比 4 大的最小数是 5。 -
交换： 数组变成
[1, 5, 8, **5**, 7, 6, **4**, 3, 1]。 -
反转尾部： 把
5后面的[7, 6, 4, 3, 1]反转，变成[1, 3, 4, 6, 7]。 -
结果：
[1, 5, 8, 5, 1, 3, 4, 6, 7]。
- 2.5
- 找前面那个较小的数。
- 找后面那个刚好大一点的数。
- 交换它俩。
- 翻转剩下的尾巴。
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;
while(j>=0&&nums[j]<=nums[i]){
j--;
}
swap(nums,i,j);
}
reverse(nums,i+1);
}
public void swap(int[] nums,int l,int r){
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
public void reverse(int[] nums,int start){
int l = start;
int r = nums.length-1;
while(l<=r){
swap(nums,l,r);
l++;
r--;
}
}
}这道题的解法非常固定，通常被称为 “两遍扫描法”。
我们可以把这个寻找过程想象成在翻越一座 “山峰”。
💡 核心步骤拆解
假设数组是：[1, 2, 7, 4, 3, 1]
第一步：找“拐点” (Find the Pivot)
从右往左看，数字通常是越来越大的（升序），这就好比你在爬山。 我们要找到 第一个开始下降 的位置。
-
1<3(升) -
3<4(升) -
4<7(升) -
7>2(降！) 停！ -
这里的
2(索引 1) 就是我们要找的“小数”，我们叫它i。 -
意义：
i后面的这一段[7, 4, 3, 1]已经是降序了（已经是这一小段能组成的最大排列），没法变更大了，必须动i这个位置才能增大。
第二步：找“大数” (Find the Successor)
既然要替换掉 2，得在它后面的那一堆人里，找一个 比 2 大，但是尽可能小 的数。 从右往左扫：
-
1<2(不行) -
3>2(行！) -
这里的
3就是我们要找的“大数”，我们叫它j。
第三步：交换 (Swap)
把 2 和 3 交换。
-
数组变成：
[1, 3, 7, 4, 2, 1] -
此时前缀变成了
1, 3...，肯定比原来的1, 2...大了。
第四步：反转 (Reverse)
这时候，交换位置后面的那段序列 [7, 4, 2, 1] 依然是降序的（最大状态）。 为了让整个数“只大一点点”，我们需要把后面这段最大状态变成最小状态（升序）。
-
直接翻转
[7, 4, 2, 1]→[1, 2, 4, 7]。 -
最终结果：
[1, 3, 1, 2, 4, 7]。
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 1. 从后往前，找到第一个 下降 的数字 (nums[i] < nums[i+1])
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// 注意：如果 i < 0，说明整个数组都是降序的（如 3,2,1），
// 那就没有下一步了，直接跳到最后一步反转即可（变回 1,2,3）。
if (i >= 0) {
// 2. 如果找到了拐点，再从后往前，找第一个比 nums[i] 大的数字
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
// 3. 交换它俩
swap(nums, i, j);
}
// 4. 把 i 后面的所有数字反转（变成升序，即最小值）
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 left = start, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
}