单调栈专题：接雨水与柱状图中最大矩形

题目列表

接雨水 42. 接雨水 - 力扣（LeetCode）

柱状图中最大的矩形 84. 柱状图中最大的矩形 - 力扣（LeetCode）

一、接雨水

1. 暴力法思路

暴力解法的本质是逐个位置计算接水量，步骤如下：

• 遍历数组中每一个位置（首尾位置无法接水，直接跳过）；
• 对每个位置 i：
  • 找 i 左边（包括 i）的最大高度 maxLeft；
  • 找 i 右边（包括 i）的最大高度 maxRight；
  • 计算该位置的接水量：min(maxLeft, maxRight) - height[i]（结果≥0 才有效）；
• 累加所有位置的接水量，得到总水量。

2. 暴力法实现代码

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            if (i == 0 || i == len - 1) {
                continue;
            }
            int maxLeft = height[i];
            int maxRight = height[i];
            for (int j = i; j >= 0; j--) {
                if (height[j] > maxLeft) {
                    maxLeft = height[j];
                }
            }
            for (int j = i; j < len; j++) {
                if (height[j] > maxRight) {
                    maxRight = height[j];
                }
            }
            sum += Math.min(maxLeft, maxRight) - height[i];
        }
        return sum;
    }
}

3. 双指针优化思路

暴力解法的最大问题是：每个位置都要重复遍历左右找最大高度。优化的核心是预处理两个数组：

• maxLeft[i]：表示位置 i 及左边的最大高度；
• maxRight[i]：表示位置 i 及右边的最大高度； 后续计算直接从预处理数组取值，无需重复遍历。

4. 双指针优化实现代码

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if (len <= 2) return 0;
        int sum = 0;
        int[] maxLeft = new int[len];
        maxLeft[0] = height[0];
        for (int i = 1; i < len; i++) {
            maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
        }
        int[] maxRight = new int[len];
        maxRight[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            maxRight[i] = Math.max(height[i], maxRight[i + 1]);
        }
        for (int i = 0; i < len; i++) {
            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        return sum;
    }
}

5. 单调栈思路

单调栈解法的核心逻辑：

1. 栈的定义：存储索引，对应高度单调递减。
2. 接水量计算：当遇到比栈顶高的元素时，说明找到凹槽右边界。弹出栈顶作为底部，新栈顶为左边界，当前索引为右边界。
   • 高度：min(height[left], height[right]) - height[mid]
   • 宽度：right - left - 1
3. 流程：遍历数组，若当前高度大于栈顶则循环弹出计算，否则压栈。

注：单调栈接水量是按行来计算的，而双指针是按列来计算的。

6. 单调栈实现代码

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if (len <= 2) return 0;
        int sum = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for (int right = 1; right < len; right++) {
            if (height[right] <= height[stack.peek()]) {
                stack.push(right);
            } else {
                while (!stack.isEmpty() && height[right] > height[stack.peek()]) {
                    int mid = stack.pop();
                    if (stack.isEmpty()) break;
                    int left = stack.peek();
                    int h = Math.min(height[left], height[right]) - height[mid];
                    int w = right - left - 1;
                    sum += h * w;
                }
                stack.push(right);
            }
        }
        return sum;
    }
}

二、柱状图中最大的矩形

1. 暴力法思路

遍历每一根柱子，向左向右找第一个高度更小的柱子作为边界，计算面积并取最大值。

2. 暴力法实现代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int sum = 0;
        for (int i = 0; i < heights.size(); i++) {
            int left = i;
            int right = i;
            for (; left >= 0; left--) {
                if (heights[left] < heights[i]) break;
            }
            for (; right < heights.size(); right++) {
                if (heights[right] < heights[i]) break;
            }
            int w = right - left - 1;
            int h = heights[i];
            sum = max(sum, w * h);
        }
        return sum;
    }
};

3. 双指针思路

通过两个数组提前计算每个柱子的左右边界，避免重复遍历，将时间复杂度从 O(n²) 降到 O(n)。

• leftMin[i]：左侧第一个更矮柱子的索引（无则为 -1）；
• rightMin[i]：右侧第一个更矮柱子的索引（无则为 n）；
• 宽度：rightMin[i] - leftMin[i] - 1。

4. 双指针实现代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if (n == 0) return 0;
        if (n == 1) return heights[0];
        int[] leftMin = new int[n];
        leftMin[0] = -1;
        for (int i = 1; i < n; i++) {
            int t = i - 1;
            while (t >= 0 && heights[t] >= heights[i]) {
                t = leftMin[t];
            }
            leftMin[i] = t;
        }
        int[] rightMin = new int[n];
        rightMin[n - 1] = n;
        for (int i = n - 2; i >= 0; i--) {
            int t = i + 1;
            while (t < n && heights[t] >= heights[i]) {
                t = rightMin[t];
            }
            rightMin[i] = t;
        }
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int width = rightMin[i] - leftMin[i] - 1;
            int area = heights[i] * width;
            maxArea = Math.max(maxArea, area);
        }
        return maxArea;
    }
}

5. 单调栈思路

使用「单调递增栈」实时找每个柱子的左右边界。哨兵的作用：头部哨兵确保栈不空，末尾哨兵强制弹出剩余元素。

• 栈内存储索引，高度递增。
• 弹出栈顶时，当前索引为右边界，新栈顶为左边界。

6. 单调栈实现代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 1) return heights[0];
        int[] newHeights = new int[len + 2];
        for (int i = 0; i < len; i++) {
            newHeights[i + 1] = heights[i];
        }
        newHeights[0] = 0;
        newHeights[len + 1] = 0;
        Deque<Integer> st = new LinkedList<>();
        st.push(0);
        int res = 0;
        for (int i = 0; i < newHeights.length; i++) {
            while (newHeights[i] < newHeights[st.peek()]) {
                int mid = st.pop();
                int right = i;
                int left = st.peek();
                int w = right - left - 1;
                int h = newHeights[mid];
                res = Math.max(res, h * w);
            }
            st.push(i);
        }
        return res;
    }
}