题解 | #单调栈#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        // 获取数组长度
        int length = nums.length;
        // 返回的结果集
        int[][] result = new int[length][2];
        // 利用双栈分别保存左边和右边的大小
        Stack<Integer> stackLeft = new Stack<>();
        Stack<Integer> stackRight = new Stack<>();
        // 数组的两边开始遍历，分别将下标记录不同的两个栈中
        for (int i = 0, j = length - 1 ; i < length; i++) {
            // 如果栈中的元素不为空并且栈顶的元素大于当前元素，则出栈
            while (!stackLeft.isEmpty() && nums[stackLeft.peek()] >= nums[i]) {
                stackLeft.pop();
            }
            // 如果栈为空，说明当前元素的最左边没有元素，所以直接赋值为-1
            if (stackLeft.isEmpty()) {
                result[i][0] = -1;
            } else {
                // 如果当前元素大于左边元素，则保存栈顶元素
                result[i][0] = stackLeft.peek();
            }
            // 当前元素的下标入栈
            stackLeft.push(i);

            while (!stackRight.isEmpty() && nums[stackRight.peek()] >= nums[j]) {
                stackRight.pop();
            }
            if (stackRight.isEmpty()) {
                result[j][1] = -1;
            } else {
                result[j][1] = stackRight.peek();
            }
            stackRight.push(j);
            j --;
        }
        return result;
    }
}