题目链接：https://leetcode.cn/problems/next-permutation/

解题思路：整数数组的 下一个排列 是指其整数的下一个字典序更大的排列，其实也就是把整数所有数字从左往右组合成一个数，则下一个排列就是将数组中的所有元素重新组合成一个数，这个数大于原来的数并且是大于原来数中最小的那个数，比如[4，5，2，6，3，1]，当前的数为452631，那个数组中的所有元素重新组合的所有新数中大于452631并且是其中最小的是453126，所以[4，5，2，6，3，1]下一个排列就是[4，5，3，1，2，6]。

有两个关键点：

1. 新组合成的数要大于原来的数

2. 下一个排列是所有大于原来的数中最小的那个数

所以：

1. 为了保证新组合成的数要大于原来的数：

从后面的数中找到一个大数，与前面的一个小数交换，就可以让其比原来的数大

2. 为了保证下一个排列是所有大于原来的数中最小的那个数：

1. 从后面找到的那个大数要尽可能小，这样才能使新的数尽可能小，比如比如452631，要想得到一个比452631大的数，需要将后面的尽可能小的大数3和前面的小数2交换得到453621

而不是让2和6交换，因为456231>453621（目标是找到一个所有大于原来的数中最小的那个数）。

2. 交换后，需要将大数后面的所有数排列成升序，这样就能保证这个数是最小的

比如452631中2和3交换后得到453621，需要将大数3后面的数排列成升序，即453126，

这样就保证了453126是所有大于原来的数中最小的那个数

算法流程如下：

1. 从后向前查找第一个升序的元素对（i，i+1），满足nums[i]<nums[i+1]，因为从从后往前找的，所以此时nums[i+1,end]一定是降序。如果找不到，说明当前就是最大的数，整个数组是降序排列的，直接翻转数组即可

2. 因为(i，i+1)是从后往前第一个升序的元素对，所以我们只需要从nums[i+1，end]中找到一个比nums[i]大的最小的大数，让其与nums[i]交换，就能保证新的数字一定比原来的数大

1. 因为nums[i+1,end]一定是降序的，所以可以从后往前找到第一个大于nums[i]的数，这个数一定就是大于nums[i]的数中最小的那个数。然后将其与nums[i]交换

2. 将num[i+1,end]中的所有元素排列成升序，注意nums[i+1,end]一定是降序。所以这一步也并不需要排序，只需要将其逆序处理即可

AC代码

class Solution {
    public static 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 static void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i]=nums[j];
        nums[j]= tem;
    }

    public static void reverse(int[] nums,int index){
        int left = index;
        int right=nums.length-1;
        while (left<right){
            int tem = nums[left];
            nums[left]=nums[right];
            nums[right]=tem;
            left++;
            right--;
        }
    }
}