直方图中最大的矩形

一句话算法

直方图最大矩形在遇到更矮柱子时，结算前面那些更高柱子能扩展出的最大面积。

问题模型

给定 $n$ 个宽度为 1 的柱子，高度为：

求直方图中能组成的最大矩形面积。

矩形必须连续，且高度不能超过区间内最矮柱子。

完整讲解见单调栈。

核心直觉

如果当前柱子比栈顶柱子更矮，那么栈顶柱子向右扩展到当前柱子之前就停止了。

弹出栈顶 mid 后：

• 高度是 h[mid]；
• 右边界是 i - 1；
• 左边界是新的栈顶 st.back() + 1；
• 宽度是 i - st.back() - 1。

于是面积为：

算法步骤

1. 在柱子序列两端加入高度为 0 的哨兵。
2. 用栈维护一个高度单调不降的下标序列。
3. 从左到右枚举当前位置 i。
4. 当栈顶柱子高度 h[st.back()] > h[i] 时，说明栈顶柱子的右边界已经确定为 i-1。
5. 弹出栈顶 mid，此时新的栈顶就是 mid 左侧第一个高度小于它的柱子。
6. 用 h[mid] * (i - st.back() - 1) 更新答案。
7. 将当前下标 i 入栈。

算法证明

核心不变量： 栈中下标对应的高度单调不降，尚未被弹出的柱子还没有确定右侧第一个更矮柱子。

1. 右边界正确。 当遇到第一个 h[i] < h[mid] 的位置时，mid 作为最低高度的矩形不能再向右跨过 i，所以右边界是 i-1。
2. 左边界正确。 弹出 mid 后，新的栈顶是左侧最近的高度小于 h[mid] 的位置。它右边一格就是 mid 能扩展到的最左位置。
3. 面积不漏。 每根柱子都会在遇到右侧第一个更矮柱子时被弹出并结算一次，这正好枚举了“以这根柱子为最低高度”的最大矩形。
4. 哨兵正确。 末尾高度 0 会强制弹出所有剩余柱子，保证每根柱子都被结算。

因此所有可能的最大矩形都会被枚举，取最大值即为答案。

复杂度分析

每个柱子最多入栈一次、出栈一次。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

        #include <bits/stdc++.h>
using namespace std;

int main() {
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;

        vector<long long> h(n + 2, 0);
        for (int i = 1; i <= n; i++) {
            cin >> h[i];
        }

        long long ans = 0;
        vector<int> st;
        st.push_back(0);

        for (int i = 1; i <= n + 1; i++) {
            while (!st.empty() && h[st.back()] > h[i]) {
                int mid = st.back();
                st.pop_back();
                long long height = h[mid];
                long long width = i - st.back() - 1;
                ans = max(ans, height * width);
            }
            st.push_back(i);
        }

        cout << ans << "\n";
    }
    return 0;
}
    

测试用例

输入：

7
2 1 4 5 1 3 3
0

输出：

8

经典例题

1. roj-3032

直方图最大矩形模板题。输入以 0 结束。

2. LeetCode 84

同一模型。可以用左右边界数组，也可以用本文的一次扫描加哨兵写法。

应用分类详解

直方图最大矩形的本质是：枚举每根柱子作为矩形最低高度时，能向左右扩展多远。

一、连续高度边界

• 典型模式： 每个元素控制一个连续区间，区间内所有元素都不小于它。
• 识别信号： 出现“矩形面积”“连续柱子”“以某个高度为限制”。
• 核心建模： 用单调栈求每个位置左侧和右侧第一个更矮柱子。

二、二维矩形转直方图

• 典型模式： 在 01 矩阵中求最大全 1 矩形。
• 识别信号： 出现“最大矩形”“全 1 子矩阵”“连续行列”。
• 核心建模： 枚举每一行作为底边，把上方连续 1 的高度转成直方图，再套本算法。