形式化题目

有 $n$ 根宽度都为 $1$、下边界都落在同一条水平基线上的矩形柱，第 $i$ 根的高度为 $h_i$。求一个完全落在这些柱子所覆盖区域内的轴对齐矩形，使它的面积最大。

设这个矩形覆盖的列区间为 $[l, r]$（下标从 $0$ 开始、闭区间），则它的高不能超过该区间内的最小高度，于是要求

正解

思路

输入的每一行是一个独立的直方图，多个用例逐个求解即可（以 n=0 结束），下面只讨论单个用例。

朴素做法与瓶颈。 把上面的式子直接写成代码：枚举左端点 $l$，向右扩展右端点 $r$ 并顺便维护区间最小值。这样是 $O(n^2)$，在 $n \leqslant 10^5$ 时约 $10^{10}$ 次操作，必然超时。瓶颈在于枚举对象是 $O(n^2)$ 个区间，而这些区间的最小值往往来自同一根柱子，被重复计算。

换一个枚举对象。 注意一个事实：任意最优矩形的高度一定等于某根柱子的高度 $h_j$。因为如果矩形高度 $H$ 不等于区间 $[l,r]$ 内的任何 $h_k$，而 $H \leqslant \min_{l \leqslant k \leqslant r} h_k$，那么把 $H$ 抬到 $\min_{l \leqslant k \leqslant r} h_k$ 仍然合法且面积更大，矛盾。所以只需对每根柱子问一句：以 $h_j$ 为高时，矩形最多能向左右各铺多远？

宽度由"第一个更矮"决定。 记

则以 $h_j$ 为高的矩形正好能覆盖开区间 $(L_j, R_j)$：再往左右延一格就会碰到高度小于 $h_j$ 的柱子。于是

枚举对象从 $O(n^2)$ 个区间降到 $n$ 根柱子。剩下的问题是：怎么在 $O(n)$ 内一次求出所有 $L_j$ 与 $R_j$。

用单调栈同时拿到两个边界。 从左到右扫描，维护一个存下标的栈，并使栈内下标对应的高度严格递增：

• 扫描到位置 $i$ 时，若 $h_i \leqslant h_{\text{top}}$，说明栈顶 top 向右已经走不动了，$i$ 就是它右边第一个更矮的位置，即 $R_{\text{top}} = i$；
• 把 top 弹出后露出的新栈顶，正是它左边第一个更矮的位置，即 $L_{\text{top}}$；
• 于是一次弹出就同时确定了左右边界，立刻结算 $h_{\text{top}} \times (i - L_{\text{top}} - 1)$，然后继续判断新的栈顶。

两个实现细节。

• 判断条件必须写成 $h_i \leqslant h_{\text{top}}$（带等号）。等高时 $i$ 并不是 top 真正的右边界，但让等高的 top 先弹出、把 $i$ 留在栈里，宽度会在 i 结算时把这些同高的列一起算进去，面积一样大；如果写成严格小于，等高的柱子会互相卡住、谁也不弹出，宽度就会算小。
• 在序列末尾追加一个高度为 $0$ 的哨兵，保证扫描结束时栈里剩下的柱子（右边没有更矮者，$R_j = n$）全都被弹出结算，不必在循环外另写一段清栈代码。高度为 $0$ 的柱子天然只贡献面积 $0$，不需要特判。

下面的剖面图把样例 2 1 4 5 1 3 3 画了出来，X 标出的就是面积 $8$ 的最优矩形（高 $4$、宽 $2$）：

1
2
3
4
5
6
7 5 |   #   
 4 |  XX   
 3 |  XX ##
 2 |# XX ##
 1 |##XX###
   +-------
    0123456

可以看出它由下标 $2,3$ 的两根柱子（高度 $4,5$）托起，左右都被下标 $1$、$4$ 的高度 $1$ 挡住——这正是 $L_2 = 1,\ R_2 = 4$，宽度 $4-1-1=2$。第二个样例 4 1000 1000 1000 1000 是四根等高柱子，正好整段铺满，面积 $1000 \times 4 = 4000$。下面是完整的扫描过程表，每一行说明"扫到哪、弹出了谁、结算出多少面积、栈里还剩什么"：

读者可以重点看第 $i=4$ 行：高度 $5$ 和 $4$ 的柱子在这一步接连被弹出，它们的右边界都是 $4$，而各自的左边界分别是弹出后的新栈顶 $2$ 和 $1$，宽度 $1$ 与 $2$ 就是这样来的。全程最大值为 $8$。

代码

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#!/usr/bin/env python3
# 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-10-01 11:16
# update_at: 2026-10-01 11:20

import sys
from itertools import chain


def max_rect(heights: list[int]) -> int:
    """返回柱状图（每根宽 1、公共基线对齐）中最大轴对齐矩形的面积。

    单调栈从底到顶按高度严格递增地存下标。弹出栈顶 j 时，新栈顶 left 是 j 左边
    第一个更矮的柱子，而当前位置 right 是 j 右边第一个更矮的柱子；所以高度
    取 heights[j] 的矩形最远只能铺满开区间 (left, right)，宽度恰好 right-left-1。
    追加一个高度 0 的哨兵（下标 n）收尾，保证每根柱子都被弹出且只结算一次。
    """
    stack: list[int] = []  # 只存下标
    best = 0
    for right, height in enumerate(chain(heights, (0,))):
        while stack and height <= heights[stack[-1]]:
            popped = stack.pop()
            left = stack[-1] if stack else -1  # 左侧第一个更矮的柱子，-1 表示没有更矮的
            best = max(best, heights[popped] * (right - left - 1))
        stack.append(right)
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    # 每个测试用例以 n 打头：n 是这组柱子的根数，n=0 是结束标记、不用处理
    for n in data:
        if n == 0:
            break
        out.append(str(max_rect([next(data) for _ in range(n)])))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(n)$（均摊）。每个下标恰好入栈一次、出栈至多一次，while 循环内所有结算的总次数为 $O(n)$；多个测试用例时按总柱数线性。
• 空间复杂度：$O(n)$。栈最多同时存 $n$ 个下标；整份输入按 token 读入另占 $O(n)$。

总结

• 本题的出发点是把答案写成区间最小值乘区间长度；朴素的区间枚举是 $O(n^2)$，瓶颈在枚举对象。
• 关键观察是"最优矩形的高一定等于某根柱子的高度"，于是改为按柱子枚举，答案变成 $h_j \times (R_j - L_j - 1)$。
• 单调递增栈在一次弹栈中同时拿到"左边第一个更矮"（新栈顶）与"右边第一个更矮"（当前扫描位置），把边界查询降到均摊 $O(1)$。
• 两个必须记住的实现细节：弹出条件带等号（h_i <= h_top），以及在末尾补一个高度 $0$ 的哨兵。前者保证等高的柱子合并结算，后者保证所有柱子都被结算。

图示解析

这张图串起本题从建模到得到答案的主线：

1
2
3
4
5
6区间最值形式
`- 最优矩形的高 = 某根柱子的高度 h_j        （抬高到区间最小值只会更大）
   `- 以 h_j 为高能铺多宽？
      `- 答案是左右第一个更矮柱子之间          h_j x (R_j - L_j - 1)
         `- 单调递增栈弹出时同时给出左边界 L_j 与右边界 R_j
            `- 末尾补哨兵 0，一次扫描结算全部柱子，均摊 O(n)

先看每一层解决的瓶颈：第一层把 $O(n^2)$ 个区间换成 $n$ 根柱子，第二层把"求左右第一个更矮"从暴力扫描换成弹栈时的均摊 $O(1)$。顺着 `- 的分支往下读，每一步都只依赖上一层已经证明过的结论。