31. 下一个排列

image.png

如何来求解呢？直接看例子
原数组nums：1 2 4 3 6 5
第一轮：从右往左遍历，去找第一次出现nums【i】>nums【i+1】,去记录nums【i】和i，
在例子中，3<6，则nums【i】=3；
第二轮：第二轮从右往左遍历，找第一个比nums【i】大的数字，记录该数字res和其索引
然后去交换nums【i】和res
在例子中，5是第一个大于3的，res=5
把3和5交换，得到1 2 4 5 6 3
然后去把nums[i+1:nums.length-1]，按升序去进行排列 1 2 4 5 3 6
为什么这样可以得到下一个排列呢？
其实也简单，如果出现第一个nums【i】>nums【i+1】，说明nums【i】之后已经排列到最大值了，只能在第i位来更换数字进行排列，那这时候，我们就去找第一个大于nums【i】的值，其实就是找到最小大于nums【i】的值，交换位置就可以。
但是，在更换第i位数字后，说明之后应该是最小值，代表不需要进行修改
自己用了比较low的方法写的，重要的是思想

class Solution {
    public void nextPermutation(int[] nums) {
        int count=1;
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]>=nums[i+1]){
                count++;
            }
        }
        if(count==nums.length){
            Arrays.sort(nums);
        }else{
        
        int temp=0;
        int temp1=0;
        int temp2=0;
        int temp3=0;
        for(int i=nums.length-1;i>=0;i--){
            if(nums[i-1]<nums[i]){
                temp=nums[i-1];
                temp1=i-1;
                break;
            }
        }

        for(int i=nums.length-1;i>=0;i--){
            if(nums[i]>temp){
               temp2=nums[i];
               temp3=i;
                break;
            }
        }


        int temp0=0;
        temp0=nums[temp1];
        nums[temp1]=nums[temp3];
        nums[temp3]=temp0;


        ArrayList<Integer> list=new ArrayList<Integer>();
        for(int i=temp1+1;i<nums.length;i++){
            list.add(nums[i]);
        }
       list.sort(Comparator.naturalOrder());
        for(int i=temp1+1;i<nums.length;i++){
            nums[i]=list.get(i-temp1-1);
        }
        }
    }
}