单调栈：解题框架与经典题

单调栈的本质

单调栈维护栈内元素单调有序（单调递增或单调递减）。
核心思路：当新元素入栈时，把破坏单调性的元素全部弹出。

适用场景：需要快速找到每个元素的"下一个更大/更小元素"、"左边第一个更大/更小"的问题。

框架：下一个更大元素（模板）

int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);         // 默认没有更大元素
    Deque<Integer> stack = new ArrayDeque<>();  // 存索引
    
    for (int i = 0; i < n; i++) {
        // 当前元素比栈顶大，栈顶找到了它的"下一个更大元素"
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int idx = stack.pop();
            res[idx] = nums[i];
        }
        stack.push(i);
    }
    return res;
}

栈中存的是还没找到"下一个更大元素"的下标（候选），保持单调递减。

例题解析

下一个更大元素 I（LeetCode 496）

int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();   // nums2 中每个元素的下一个更大元素
    Deque<Integer> stack = new ArrayDeque<>();
    for (int x : nums2) {
        while (!stack.isEmpty() && x > stack.peek())
            map.put(stack.pop(), x);
        stack.push(x);
    }
    // nums1 的元素都在 nums2 中
    return Arrays.stream(nums1).map(x -> map.getOrDefault(x, -1)).toArray();
}

每日温度（LeetCode 739）

int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();  // 存下标
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()])
            res[stack.peek()] = i - stack.pop();   // 距离 = 当前下标 - 弹出下标
        stack.push(i);
    }
    return res;
}

循环数组：下一个更大元素 II（LeetCode 503）

处理循环：将数组遍历两遍（或对下标取模）。

int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < 2 * n; i++) {            // 遍历两圈
        int x = nums[i % n];
        while (!stack.isEmpty() && x > nums[stack.peek()])
            res[stack.pop()] = x;
        if (i < n) stack.push(i);                 // 只入栈一次
    }
    return res;
}

经典难题：柱状图中最大的矩形

接雨水（LeetCode 42）

直觉：每一列能盛的水 = min(左侧最大高度, 右侧最大高度) - 当前高度。

单调栈解法（逐行计算）：

int trap(int[] height) {
    int res = 0;
    Deque<Integer> stack = new ArrayDeque<>();  // 单调递减栈
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottom = stack.pop();           // 凹槽底部
            if (stack.isEmpty()) break;
            int left = stack.peek();
            int w = i - left - 1;              // 宽度
            int h = Math.min(height[left], height[i]) - height[bottom];  // 高度
            res += w * h;
        }
        stack.push(i);
    }
    return res;
}

柱状图中最大的矩形（LeetCode 84）

int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] newH = new int[n + 2];  // 首尾加哨兵 0，避免特判
    System.arraycopy(heights, 0, newH, 1, n);
    int res = 0;
    Deque<Integer> stack = new ArrayDeque<>();  // 单调递增栈
    for (int i = 0; i < newH.length; i++) {
        while (!stack.isEmpty() && newH[i] < newH[stack.peek()]) {
            int h = newH[stack.pop()];
            int w = i - stack.peek() - 1;
            res = Math.max(res, h * w);
        }
        stack.push(i);
    }
    return res;
}

单调栈 vs 前缀最大值

总结

单调栈的口诀：

1. 入栈之前，弹出破坏单调性的元素，弹出时记录答案
2. 栈中存的是"等待被处理"的元素（找到更大/更小后写答案）
3. 遇到循环数组，遍历两圈
4. 在数组两端加哨兵（0 或 INT_MAX），避免空栈判断