84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

img

1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

img

1
2
输入： heights = [2,4]
输出： 4

解题思路

该解法是对单调栈思路的优化实现，通过在数组末尾添加哨兵元素和栈初始化技巧，将左右边界的计算合并到一次遍历中，代码更简洁且效率更高。

核心优化思路

哨兵元素（Sentinel）：

  • 在原数组末尾添加 -1（高度为负数的哨兵），确保遍历结束时栈中所有元素都会被弹出计算（相当于 “大火收汁”）；
  • 栈初始时推入 -1（索引哨兵），解决栈空时的边界判断问题，同时自然对应 “左侧无更矮柱子” 的情况（left[i] = -1）。

一次遍历计算左右边界：

  • 遍历每个元素作为右侧边界（right），当当前高度小于栈顶高度时，栈顶元素的左右边界均已确定：
    • 右边界：当前索引 right（第一个比栈顶元素矮的位置）；
    • 左边界：弹出栈顶后，新的栈顶索引（第一个比栈顶元素矮的左侧位置）；
  • 弹出栈顶元素时直接计算其对应的最大矩形面积，无需额外存储左右边界数组。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(-1); // 最后大火收汁，用 -1 把栈清空
        stack<int> st;
        st.push(-1); // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        int ans = 0;
        for (int right = 0; right < heights.size(); right++) {
            int h = heights[right];
            while (st.size() > 1 && heights[st.top()] >= h) {
                int i = st.top(); // 矩形的高（的下标）
                st.pop();
                int left = st.top(); // 栈顶下面那个数就是 left
                ans = max(ans, heights[i] * (right - left - 1));
            }
            st.push(right);
        }
        return ans;
    }
};

作者：灵茶山艾府
链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/solutions/2695467/dan-diao-zhan-fu-ti-dan-pythonjavacgojsr-89s7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。