题解 | #单调栈#

import java.util.*;

/**
 * 单调栈的简单运用
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> stackIndex = new Stack<>();
        int[][] ret = new int[nums.length][2];
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() >= nums[i]) {
                stackIndex.pop();
                stack.pop();
            }
            ret[i][1] = stack.isEmpty() ? -1 : stackIndex.peek();
            stack.push(nums[i]);
            stackIndex.push(i);
        }
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stackIndex1 = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack1.isEmpty() && stack1.peek() >= nums[i]) {
                stack1.pop();
                stackIndex1.pop();
            }
            ret[i][0] = stack1.isEmpty() ? -1 : stackIndex1.peek();
            stack1.push(nums[i]);
            stackIndex1.push(i);
        }
        return ret;
    }
}