【LeetCode】Day44-下一个排列

题目

31. 下一个排列【中等】（似乎字节很爱考

题解

不知道咋描述了，硬记吧…

中心思想就是，我想让下一个数比当前数大，但是大的幅度又最小

方法描述如下，参考自最高赞回答：

1. 从后往前找第一个低谷A[i],i后是山峰
2. 从后往前找第一个比低谷高的元素A[j]
3. 交换A[i],A[j]
4. 这时 [j,end) 必然是降序，逆置[j,end)
5. 如果在步骤 1 找不到低谷，说明当前 [begin,end) 一直在下降，则直接跳到步骤 4

class Solution {
    public void nextPermutation(int[] nums) {
        int n=nums.length;
        int i=n-2;
        // 从后往前找第一个低谷i,i后是山峰
        for(;i>=0;i--){
            if(nums[i]<nums[i+1]){
                break;
            }
        }
        if(i>=0){
            // 从后往前找第一个比低谷高的元素j
            int j=n-1;
            for(;j>i+1;j--){
                if(nums[j]>nums[i]){
                    break;
                }
            }
            // 交换i,j
            swap(nums,i,j);
        }
        // 逆置山峰及其后所有元素
        reverse(nums,i+1);
    }
    // 交换数组两元素
    public void swap(int nums[],int i,int j){
        int tmp=nums[j];
        nums[j]=nums[i];
        nums[i]=tmp;
    }
    // 逆置begin及其后所有元素
    public void reverse(int nums[],int begin){
        int n=nums.length;
        for(int i=0;i<(n-begin)/2;i++){
            swap(nums,begin+i,n-1-i);
        }
    }
}

时间复杂度： O ( n ) O(n) O(n)，我们至多只需要扫描两次序列，以及进行一次反转 *** 作。

空间复杂度： O ( 1 ) O(1) O(1)