单调栈（每日温度 · 接雨水 · 柱状图最大矩形）

单调栈核心思想

维护一个单调递增/递减的栈，当新元素不满足单调性时，弹出栈元素并处理。

• 单调递减栈：栈中元素从栈底到栈顶单调递减，用来找右侧第一个比它大的元素（下一个更大元素）
• 单调递增栈：用来找右侧第一个比它小的元素

每日温度（LeetCode 739）

对每一天，找到下一个温暖天（温度更高的天）在几天后：

int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();  // 存下标，单调递减栈

    for (int i = 0; i < n; i++) {
        // 当前温度比栈顶更高，栈顶找到了"下一个更暖的天"
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            answer[idx] = i - idx;
        }
        stack.push(i);
    }
    return answer;
}

下一个更大元素 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++) {
        while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
            res[stack.pop()] = nums[i % n];
        }
        if (i < n) stack.push(i);
    }
    return res;
}

接雨水（LeetCode 42）

单调栈做法（理解水平层）：

int trap(int[] height) {
    int water = 0;
    Deque<Integer> stack = new ArrayDeque<>();  // 单调递减栈

    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int mid = stack.pop();
            if (stack.isEmpty()) break;
            int left = stack.peek();
            int h = Math.min(height[left], height[i]) - height[mid];
            int w = i - left - 1;
            water += h * w;
        }
        stack.push(i);
    }
    return water;
}

双指针做法（更简洁，记住这个）：

int trapTwoPointer(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (leftMax < rightMax) water += leftMax - height[left++];
        else water += rightMax - height[right--];
    }
    return water;
}

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

单调递增栈：当当前高度小于栈顶时，以栈顶为高度计算矩形面积：

int largestRectangleArea(int[] heights) {
    // 首尾加哨兵，高度为 0，简化边界处理
    int n = heights.length;
    int[] h = new int[n + 2];
    System.arraycopy(heights, 0, h, 1, n);
    // h[0] = h[n+1] = 0（默认）

    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;

    for (int i = 0; i < h.length; i++) {
        // 单调递增栈：遇到收缩时计算面积
        while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
            int height = h[stack.pop()];
            int width = i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

关键点：当弹出元素时，宽度 = 当前下标 - 新栈顶下标 - 1，体现了"这是能以该高度延伸的最大宽度"。