单调栈模板：一眼识别“下一个更大元素”类问题#

class Solution {
    public int[] nextGreaterElement(int[] nums) {
        int length = nums.length; // 数组长度
        int[] answer = new int[length]; // answer[i]：nums[i] 右侧第一个更大元素值
        Arrays.fill(answer, -1); // 默认不存在更大元素时返回 -1
        Deque<Integer> stack = new ArrayDeque<>(); // 维护“值单调递减”的下标栈

        for (int index = 0; index < length; index++) { // 从左到右扫描
            while (!stack.isEmpty() && nums[index] > nums[stack.peek()]) { // 一旦当前值更大，可结算一批栈顶元素
                int prevIndex = stack.pop(); // 被结算元素的下标
                answer[prevIndex] = nums[index]; // 当前值就是它右侧第一个更大值
            }
            stack.push(index); // 当前下标入栈，后续等待更大元素
        }

        return answer; // 返回全部位置的结算结果
    }
}

class Solution {
    public int[][] nearestSmaller(int[] nums) {
        int length = nums.length; // 元素个数
        int[] left = new int[length]; // left[i]：i 左侧最近更小元素下标，不存在为 -1
        int[] right = new int[length]; // right[i]：i 右侧最近更小元素下标，不存在为 length
        Arrays.fill(left, -1); // 初始化左边界哨兵
        Arrays.fill(right, length); // 初始化右边界哨兵
        Deque<Integer> stack = new ArrayDeque<>(); // 维护单调递增栈（按值）

        for (int index = 0; index < length; index++) { // 扫描每个位置
            while (!stack.isEmpty() && nums[index] < nums[stack.peek()]) { // 当前值更小，触发栈顶元素右边界结算
                right[stack.pop()] = index; // 栈顶元素右侧最近更小下标就是当前 index
            }
            if (!stack.isEmpty()) { // 栈顶是当前元素左侧最近且更小的候选
                left[index] = stack.peek(); // 记录左边界
            }
            stack.push(index); // 当前元素入栈，供后续元素结算
        }

        return new int[][]{left, right}; // 同时返回左右最近更小边界
    }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length; // 柱子数量
        Deque<Integer> stack = new ArrayDeque<>(); // 维护“高度递增”的下标栈
        int maxArea = 0; // 记录最大矩形面积

        for (int index = 0; index <= length; index++) { // 多跑一步用于放置结尾哨兵
            int currentHeight = index == length ? 0 : heights[index]; // 哨兵高度 0 强制清空栈并结算剩余柱子

            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) { // 当前柱子更矮，说明栈顶柱子右边界确定
                int height = heights[stack.pop()]; // 以被弹出柱子的高度作为矩形高
                int leftIndex = stack.isEmpty() ? -1 : stack.peek(); // 弹出后新的栈顶是其左侧第一个更矮柱子
                int width = index - leftIndex - 1; // 宽度 = 右边界(不含) - 左边界(不含)
                maxArea = Math.max(maxArea, height * width); // 更新最大面积
            }

            stack.push(index); // 当前柱子下标入栈
        }

        return maxArea; // 返回最大矩形面积
    }
}