31. Next Permutation

class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length<=1)return;
        boolean flag = false;
        int i = nums.length-2;
        for(;i>=0;i--){
            if(nums[i]<nums[i+1]){
                break;
            }
        }
        int p = i+1, q = nums.length-1;
        //翻转逆序数组
        while(p<q){
            int tmp = nums[p];
            nums[p] = nums[q];
            nums[q] = tmp;
            p++;
            q--;
        }
        if(i!=-1){
            //回溯找到nums[i]的插入位置
            for(int k=i+1;k<nums.length;k++){
                if(nums[i]<nums[k]){
                    int tmp = nums[i];
                    nums[i] = nums[k];
                    nums[k] = tmp;
                    flag = true;
                    break;
                }
            }
        }    
    }
}