84. 柱状图中最大的矩形

难度：🔴 Hard | 标签：单调栈 | 状态：⬜ LeetCode 链接

思路

对每根柱子求「以它为高」能扩展的最大矩形 = 左右第一个更矮位置围出来的宽度 × 高。 单调递增栈：栈顶比当前矮的全弹出，弹出时计算面积。

两端加 0 哨兵简化边界。

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        vector<int> a = {0};
        a.insert(a.end(), h.begin(), h.end());
        a.push_back(0);
        stack<int> st;
        int best = 0;
        for (int i = 0; i < (int)a.size(); ++i) {
            while (!st.empty() && a[i] < a[st.top()]) {
                int j = st.top(); st.pop();
                int w = i - st.top() - 1;
                best = max(best, a[j] * w);
            }
            st.push(i);
        }
        return best;
    }
};

复杂度

• 时间 O(n)，空间 O(n)

易错 / 回顾

• 两端 0 哨兵让左右边界自然清空
• 宽度 = i - 新栈顶 - 1（弹出 j 后的新栈顶就是 j 左边的较矮元素）
• 与「最大矩形」（85）联动：每行视为柱状图