最大的矩形

形式化题目

给定 $n$ 根宽度都是 $1$ 的相邻柱子，高度分别为 $h_1, \dots, h_n$ 。选择一段连续柱子作为矩形底边，矩形高度只能取这段柱子的最低高度，求能放下的最大矩形面积。

思路

朴素做法枚举连续区间，并在扩展右端点时维护最低柱高：

cpp

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
34
35
36
37
38
39/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:46
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long h[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    long long ans = 0;
    // 枚举矩形覆盖的连续区间 [left, right]。
    for (int left = 1; left <= n; left++) {
        long long lowest = h[left];
        for (int right = left; right <= n; right++) {
            lowest = min(lowest, h[right]);
            long long area = lowest * (right - left + 1);
            ans = max(ans, area);
        }
    }

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

它有 $O(n^2)$ 个区间，不能处理 $n=10^5$ 。

单调栈思想

固定一根柱子 mid 作为最低高度时，只要找到它左右不能继续扩展的位置，就能计算一个候选矩形。用单调递增栈保存尚未确定右边界的柱子下标。扫描到高度低于栈顶的柱子 i 时，栈顶 mid 的右边界已确定为 i-1；弹栈后的新栈顶 left 给出左边界，面积为：

h_{mid}\times(i-left-1)

实现中也弹出相等高度的旧柱子，让较新的同高柱继承旧柱子的左侧扩展范围，使栈内高度始终严格递增。相等时旧柱子的计算只是冗余候选，最终较新的同高柱会得到不小于它的宽度。末尾补一个高度为 $0$ 的哨兵，保证栈中剩余柱子全部结算。

弹栈过程演示

下表展示官方样例中每次弹栈如何确定一个候选矩形：

扫描位置	当前高度	本次结算的矩形	入栈后下标栈
1	3	无	[1]
2	1	高 3，区间 [1, 1]，面积 3	[2]
3	6	无	[2, 3]
4	5	高 6，区间 [3, 3]，面积 6	[2, 4]
5	2	高 5，区间 [3, 4]，面积 10	[2, 5]
6	3	无	[2, 5, 6]
n+1（右哨兵）	0	高 3，区间 [6, 6]，面积 3；高 2，区间 [3, 6]，面积 8；高 1，区间 [1, 6]，面积 6	[n+1]

第 5 根柱子到来时，高度为 5 的第 4 根柱子被结算。它左侧的新栈顶是第 2 根柱子，右侧限制位置是第 5 根柱子，因此能覆盖 [3, 4]，正好得到样例答案 10。每个下标只会入栈和出栈各一次；过程表中所有弹栈操作加起来也是线性的。

代码

cpp

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
34
35
36
37
38
39
40
41
42
43
44
45
46/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:46
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long h[MAXN];
int st[MAXN], top;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    // 右端补一个高度为 0 的柱子，统一结算栈中剩余矩形。
    h[n + 1] = 0;
    long long ans = 0;

    for (int i = 1; i <= n + 1; i++) {
        // 更矮柱子确定右边界；相等高度则由新下标替代旧下标。
        while (top > 0 && h[st[top]] >= h[i]) {
            int mid = st[top];
            top--;

            int left = st[top];
            long long width = i - left - 1;
            long long area = h[mid] * width;
            ans = max(ans, area);
        }
        st[++top] = i;
    }

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

复杂度

每根柱子最多入栈、出栈各一次，时间复杂度为 $O(n)$ 。下标栈最多保存 $n+1$ 个位置，空间复杂度为 $O(n)$ 。

总结

柱状图最大矩形的关键是：不枚举每根柱子的左右边界，而是在单调栈弹出时结算一根柱子的最大延伸宽度。右侧补的哨兵和宽度 i-left-1 是实现中最容易出错的两处。

图示解析

这张图串起本题从直方图到最大面积的主线：

text

1
2
3
4
5每根柱子的高度
`- 把它看成候选矩形的最低高度
   `- 找到左右不能继续延伸的位置
      `- 单调递增栈在高度下降时结算该柱子
         `- 高度 x 可延伸宽度，取所有候选的最大值

先把“找左右边界”的工作交给栈，而不是为每根柱子分别向两边扫描。每根柱子入栈一次、出栈一次，因此所有候选矩形能在线性时间内结算完。右侧补的高度 0 哨兵只负责触发最后一批结算，不代表真实柱子。

目录

形式化题目

思路

单调栈思想

弹栈过程演示

代码

复杂度

总结

图示解析