单调栈

典型的单调栈的思想做题

public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int len = nums.length;
        // 返回的数组构造
        int[][] ans = new int[len][2];
        // 用栈保存
        Stack<Integer> stack = new Stack<>();
        // 从左往右，依次进行入栈，保存从左到右的升序的值
        for(int i = 0; i < len; i++){
            // 如果栈里面的值都比其大，就pop
            while(!stack.isEmpty() && nums[stack.peek()] > nums[i]) stack.pop();
            // 栈空，说明nums[i]左边没有比他小的值
            if(stack.isEmpty()){
                ans[i][0] = -1;
            } else {
                // 如果有比他小的，那么栈中的第一个元素的值就是离他最近的
                ans[i][0] = stack.peek();
            } 
            stack.push(i);
        }
        // 思路跟上面的一样，从右往左，保存升序值
        stack.clear();
        for(int i = len - 1; i >= 0; i--){
            while(!stack.isEmpty() && nums[stack.peek()] > nums[i]) stack.pop();
            if(stack.isEmpty()){
                ans[i][1] = -1;
            } else {
                ans[i][1] = stack.peek();
            }
            stack.push(i);
        }
        return ans;
    }