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]

示例 4： 输入：nums = [1] 输出：[1]

提示： 1 <= nums.length <= 100 0 <= nums[i] <= 100

2.思路

（1）双指针 思路参考该。

想得到当前排列在字典序中下一个更大的排列，则需要将前面的“小数”与后面的”大数“进行交换，并且还要保证下一个数的增加幅度最小，这样就能得到符合条件的排列。为此需要： ① 从数组后面向前找第一个升序元素对 (nums[i], nums[i + 1])，即 nums[i] < nums[i + 1]，其中从后向前找是为了尽量在低位上交换，以保证下一个数增加的幅度最小； ② 在 nums[i + 1…nums.length - 1] 中从后向前查找第一个大于 nums[i] 的值 nums[j]，然后交换它们的值； ③ 最后将 nums[i + 1] ~ nums[nums.length - 1] 从降序变成升序即可，由于前面已经将 nums[i] 与 nums[j] (nums[i] < nums[j]) 进行了交换，即新得到的排列已经比原来的大，但为了保证增加的幅度最小，所以需要将 nums[i] 后面的序列变成降序。

3.代码实现（Java）

//思路1————双指针
class Solution {
          
   
    public void nextPermutation(int[] nums) {
          
   
        int i = nums.length - 2;
        //从数组后面向前找第一个升序元素对(nums[i], nums[i + 1])，即 nums[i] < nums[i + 1]
        while (i >= 0 && nums[i] >= nums[i + 1]) {
          
   
            i--;
        }
        //若 i >= 0，则已经找到升序元素对
        if (i >= 0) {
          
   
            int j = nums.length - 1;
            //在 nums[i + 1...nums.length - 1] 中从后向前查找第一个大于 nums[i] 的值 nums[j]
            while (j >= 0 && nums[j] <= nums[i]) {
          
   
                j--;
            }
            //交换 nums[i] 和 nums[j] 的值
            swap(nums, i, j);
        }
        //将 nums[i + 1] ~ nums[nums.length - 1] 反转，即从降序变成升序
        reverse(nums, i + 1);
    }
    
    //将 nums[start] ~ nums[nums.length - 1]反转
    public void reverse(int nums[], int start) {
          
   
        int i = start;
        int j = nums.length - 1;
        while (i < j) {
          
   
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    
    //交换 nums[i] 和 nums[j] 的值
    public void swap(int[] nums, int i, int j) {
          
   
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}