直方图中最大的矩形

一句话算法

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

问题模型

给定 $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;
}
    

        
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

        # 单调栈求直方图最大矩形面积。
# h 为 1 下标高度数组（h[1..n]），要求高度非负；函数内部按 C++ 版补齐 h[0] = h[n+1] = 0 两个哨兵。
# 对每个柱子 mid，左右两端第一个比它矮的柱子夹出的宽度就是它能撑起的最大宽度；
# 用递增单调栈，遇到更矮的 h[i] 时弹出并结算 mid 的面积。
# C++ 用 long long 防 height * width 溢出 int；Python int 任意精度，该坑不存在。
# 调用示例：largest_rectangle([0, 2, 1, 5, 6, 2, 3]) -> 10

type Arr = list[int]  # 1 下标数组，h[0] 占位不用


def largest_rectangle(h: Arr) -> int:
    """返回直方图中最大矩形面积；h 长度至少为 1（n = len(h) - 1，n = 0 时返回 0）。"""
    n = len(h) - 1

    # 复制成 n+2 长度并补上左右哨兵 0：保证栈底恒有 h[0]=0 兜底，且最后 i=n+1 能弹空栈。
    hs = [0] * (n + 2)
    for i in range(1, n + 1):
        hs[i] = h[i]

    answer = 0
    st: Arr = [0]  # 栈内存下标，对应高度单调不减

    for i in range(1, n + 2):
        while hs[st[-1]] > hs[i]:
            mid = st.pop()
            height = hs[mid]
            width = i - st[-1] - 1  # 左右第一个更矮柱子之间的宽度
            area = height * width
            if area > answer:
                answer = area
        st.append(i)

    return answer
    

测试用例

输入：

7
2 1 4 5 1 3 3
0

输出：

8

经典例题

1. roj-3032

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

2. LeetCode 84

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

应用分类详解

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

一、连续高度边界

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

二、二维矩形转直方图

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