---

题目

• 原题连接：31. 下一个排列

---

1- 思路

思路

• ① 从右边找出一个尽可能大的数，和左边的数进行交换 ——> 交换后得到的数 就是 字典序更高
• ② 字典序高，但不代表其就是下一个 ——> 如何找下一个？
  • 左边的小数，尽可能靠右
  • 右边的大数，尽可能的小（比左边的小数大一点点）

目标

• ① 找到数组的拐点 ——> 从右向左遍历 ——> nums[i] < nums[i+1] 则找到了拐点 i+1
• ② 找到拐点右侧第一个 nums[i] 大的元素，此时记录 为 j ——> 从右向左遍历
• ③ 将元素 i 和 元素 j 交换，之后 sort(i+1,len-1)
• ④ 如果不存在拐点，此时直接 reverse 整个数组

---

2- 实现

⭐31. 下一个排列——题解思路

java">class Solution {public void nextPermutation(int[] nums) {int len = nums.length-1;int i = len-1,j;// 1. 找拐点for(; i>=0 ;i--){if(nums[i] < nums[i+1]) break;}// 最大序列直接 reverseif(i==-1){int L = 0;int R = len;while(L<=R){swap(nums,L++,R--);}return;}// 2. 有拐点for( j = len; j>=i+1 ; j--){if(nums[j] > nums[i]) break;}swap(nums,i,j);// 实现 Reverseint L = i+1;int R = len;while(L<=R){swap(nums,L++,R--);}return;}public void swap(int[] nums,int i ,int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

---

3- ACM 实现

java">public class nextPL {public static void nextPL(int[] nums){// 1.找拐点，从右往左int len = nums.length-1;int i ,j;for( i = len-1 ; i >= 0 ; i--){if(nums[i] < nums[i+1]) break;}if(i==-1){int L = 0;int R = len;while(L<=R){swap(nums,L++,R--);}return;}// 2. 找第一个小值for(j = len;j>=i+1;j--){if(nums[j] > nums[i]) break;}// 3. 先交换swap(nums,i,j);// 4. reverseint L = i+1;int R  = len;while(L<=R){swap(nums,L++,R--);}return;}// 定义 swap 函数public static void swap(int[] nums,int i ,int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入数组长度");int n = sc.nextInt();int[] nums = new int[n];for(int i = 0;  i < n; i++){nums[i] = sc.nextInt();}nextPL(nums);System.out.println("下一个排列是");for(int i : nums){System.out.print(i+" ");}}
}

---