题解 | #下一个排列#

我们知道正序是最小的，倒序是最大的。因此我们可以从后往前去找第一个非倒序的值，然后用这个值去跟倒序数里面比它大的第一个数进行交换即可。最后记得反转逆序数组。 特殊情况： 倒序 直接返回正序
size == 1直接返回原数组

import java.util.*;

public class Solution {
    public int[] nextPermutation (int[] nums) {
        // write code here
        int n = nums.length;
        if(nums.length == 1){
            return nums;
        }
        int k = n-1;
        while(k-1>=0&&nums[k-1] > nums[k]){
            k--;
        }
        if(k==0){
            Arrays.sort(nums);
            return nums;
        }
        k--;
        int t = k;
        while(t + 1 <n && nums[t+1] > nums[k]){
            t++;
        }
        swap(nums,k,t);
        k = k+1;
        while(k<t){
            swap(nums,k++,t--);
        }
    
        return nums;
         
    }
    void swap(int[]nums,int a,int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}