下一个大/小/排列的数->单调栈

下一个大/小/排列的数 等等题目， 要能想到和单调栈相关

如：
下一个数：https://leetcode.cn/problems/next-permutation/description/

class Solution {
    public void nextPermutation(int[] nums) {
       nextPermutation_stack(nums);
    }


    // 使用单调栈实现
    public void nextPermutation_stack(int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        int idxOfBigger = nums.length;
        int idxOfSmaller = -1;
        for(int i = nums.length - 1; i >= 0; -- i) {
            boolean poped = false;
            while(false == stack.isEmpty() && nums[i] < nums[ stack.peek()]) {
                idxOfBigger = stack.pop();
                poped = true;
            }
            if(poped) {
                idxOfSmaller = i;
                break;
            }else {
                stack.push(i);
            }

        }
        if(idxOfSmaller == -1 ) {
            for(int i = 0; i < nums.length / 2; ++ i) {
                int tmp = nums[i];
                nums[i] = nums[nums.length - 1 - i];
                nums[nums.length - 1 - i] = tmp;
            }
            return;
        }
        exch(nums, idxOfBigger, idxOfSmaller);
        quictSort(nums, idxOfSmaller + 1, nums.length - 1);

    }


    // 加一个自己实现的快排
    public void quictSort(int[] nums, int lo, int hi) {
        if(lo >= hi) {
            return;
        }
        int j = partition(nums, lo, hi);
        quictSort(nums, lo, j-1);
        quictSort(nums, j+1, hi);

    }

    public int partition(int[] nums, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int v = nums[lo];
        while(true){
            //扫描左边，若结束，则当前元素大于或者等于了切分元素，或者已经到了边界
            while(nums[++i] < v){
                if (i == hi){
                    break;
                }
            }
            //扫描右边，若结束，则当前元素小于或者等于了切分元素，或者已经到了边界
            while(v <nums[--j]){
                if (j == lo){
                    break;
                }
            }        
            //运行到这里 如果i == j 则说明 a[i] 也就是a[j]  等于切分元素
            //如果i > j ,说明a[i] > 元素v  a[j] < v
            //两种情况下，直接跳出循环，并且置换lo j 的元素，不然就是还没相遇，那么交换i j
            if(i >= j){
                break;
            }
            exch(nums , i , j);
        }
        exch(nums , lo , j);
        return j;
    }

    static void exch(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
     

    // 使用我的笨方法
    public void nextPermutation_stupid(int[] nums) {
        int maxP = -1;
        int maxQ = nums.length;
        for(int i = nums.length - 1; i > 0 && i > maxP ;  --i) {
            for( int j = 0; j < i; ++j) {
                if(nums[i] > nums[j]) {
                    if(j > maxP) {
                        maxP = j;
                        maxQ = i;
                    }
                }
            }
        }
        if(maxP == -1) {
            for(int i = 0; i < nums.length / 2; ++ i) {
                int tmp = nums[i];
                nums[i] = nums[nums.length - 1 - i];
                nums[nums.length - 1 - i] = tmp;
            }
            return;
        }

        int tmp = nums[maxP];
        nums[maxP] = nums[maxQ];
        nums[maxQ] = tmp;
        // int[] ts = new int[nums.length - maxP - 1];
        // for(int i = maxP + 1; i < nums.length; ++i ) {
        //     ts[i - maxP - 1] = nums[i];
        // }
        // Arrays.sort(ts);
        // for(int i = maxP + 1; i < nums.length; ++i ) {
        //     nums[i] = ts[i - maxP - 1];
        // }

        // 把上面的替换为 快排实现
        quictSort(nums, maxP + 1, nums.length -1);

    }    
}