最大矩形面积 (赛博朋克版) —— 单调栈经典两次遍历法

 题目描述：赛博朋克：巨幅霓虹广告

【题目背景】 在霓虹闪烁的夜之城，林立的高楼大厦构成了一道参差不齐的城市天际线。为了迎接即将到来的“星际狂欢节”，超级巨头“荒坂科技”计划在市中心的一排建筑外墙上，挂起一块史无前例的巨幅矩形全息霓虹广告牌。

【题目详情】 市中心共有n栋紧挨着的大楼排成一列。已知第i栋大楼的高度为h[i]。每栋大楼的宽度均可以视为1。

为了保证广告牌的平整和安全，这块巨幅矩形广告牌必须紧贴着大楼的表面安装，且广告牌的任何部分都不能超出其所覆盖大楼的高度（也就是说，如果广告牌跨越了多栋大楼，它的最高点受限于这些大楼中最矮的那一栋）。

请计算出这块全息霓虹广告牌的最大可能面积。

【输入格式】 第一行包含一个整数n，表示大楼的总数。 第二行包含 n 个整数h[1],h[2], …, h[n]，相邻两个数之间用单个空格隔开，表示从左到右每栋大楼的高度。

【输出格式】 输出一行，包含一个整数，表示这块全息霓虹广告牌的最大可能面积。

【样例输入】

7
2 4 4 6 4 3 1

【样例输出】

16

【样例解释】 选择第 2、3、4、5 栋大楼，它们的高度分别是 4, 4, 6, 4。如果广告牌跨越这四栋大楼，高度最高只能取决于最矮的大楼（高度为4）。 此时广告牌的宽度为4，高度为4，总面积为 4*4=16。这是所有可能方案中面积最大的一种。 (注：如果选第1到6栋大楼，高度受限于最矮的 2，宽度为6，面积为12；不如16 大。)

【数据范围】 对于100%的数据，保证 1<=n<= 200000，1<=h[i]<= 10^9。

题目分析

本题是一道非常经典的算法题（同 LeetCode 84：柱状图中最大的矩形）。 核心切入点： 任何一个矩形，它的高度一定是由构成这个矩形的最矮的那根柱子决定的。 因此，我们可以转换思路：枚举每一根柱子，假设它是最终矩形中最矮的那根（即矩形的高度就是这根柱子的高度），那么这个矩形能向左、向右延伸多远？

• 向右延伸的极限： 遇到右边第一个比它矮的柱子就得停下。

• 向左延伸的极限： 遇到左边第一个比它矮的柱子就得停下。

只要帮每根柱子找到这两个边界，算出宽度，再乘以它自己的高度，就能求出以它为高度的最大面积。最后在所有柱子算出的面积中取最大值即可。

 思考过程与算法设计

为了逻辑最清晰、最不易出错，我们采用单调栈的两次遍历策略：

第一步：从左向右扫描，找右边界r[i]

• 维护一个存储下标的单调栈（栈底到栈顶对应的高度严格递增）。

• 当遍历到第i根柱子时，如果它的高度小于栈顶柱子的高度，说明第i根柱子就是栈顶柱子“右边第一个比它矮的”。

• 记录 r[s.top()]=i，并将栈顶弹出。

• 遍历结束后，栈里剩余元素的右边界假定在数组最右侧的外面，即n+1。

第二步：从右向左扫描，找左边界l[i]

• 清空栈，使用完全相同的逻辑，只不过循环方向变成从 n 到 1。

• 如果当前柱子矮于栈顶，说明当前柱子是栈顶柱子“左边第一个比它矮的”。

• 记录 l[s.top()]=i。

• 遍历结束后，栈里剩余元素的左边界假定在数组最左侧的外面，即 0。

第三步：计算面积

• 遍历所有柱子，计算以第 i 根柱子为高的矩形宽度：宽度=r[i]-l[i]- 1。

• 计算面积并更新全局最大值。

时空复杂度分析

• 时间复杂度：O(n)。寻找右边界时，每根柱子最多入栈一次、出栈一次；寻找左边界时同理。两次遍历的总操作次数与n呈线性关系。最后的面积计算也是O(n)。

• 空间复杂度：O(n)。使用了三个大小为n的数组（h, l, r）以及一个单调栈，空间占用随n线性增长。

易错点总结

完整代码

//最大矩形面积
#include <iostream>
#include <stack>
#include <algorithm>//对应max
using namespace std;
int n;
long long h[200010];//每一列格子涂色的高度
stack<int> s;//单调栈 存放下标
int l[200010];//l[i]代表i左边第一个高度小于它的格子的下标
int r[200010];//r[i]代表i右边第一个高度小于它的格子的下标

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
//先找每个格子右边第一个高度小于它的格子的下标
for(int i=1;i<=n;i++){
//如果栈非空 且当前格子高度矮于栈顶格子
while(!s.empty()&&h[i]<h[s.top()]){
r[s.top()]=i;//栈顶格子右边第一个比栈顶格子矮的格子的下标记录下来
s.pop();//栈顶格子出栈
}
//当栈为空或当前格子高度大于等于栈顶格子
//入栈
s.push(i);
}
//栈内最后剩下的格子都是右边没有比他们矮的格子，所以记录为n+1（最后一个格子后面）
while(!s.empty()){
r[s.top()]=n+1;
s.pop();
}
//先找每个格子左边第一个高度小于它的格子的下标
for(int i=n;i>=1;i–){
//如果栈非空 且当前格子高度矮于栈顶格子
while(!s.empty()&&h[i]<h[s.top()]){
l[s.top()]=i;//栈顶格子左边第一个比栈顶格子矮的格子的下标记录下来
s.pop();//栈顶格子出栈
}
//当栈为空或当前格子高度大于等于栈顶格子
//入栈
s.push(i);
}
//栈内最后剩下的格子都是左边没有比他们矮的格子，所以记录为0（第一个格子前面）
while(!s.empty()){
l[s.top()]=0;
s.pop();
}
long long ma=0;//记录最大面积
//遍历所有各自计算最大面积
for(int i=1;i<=n;i++){
ma=max(ma,(r[i]-l[i]-1)*h[i]);
}
cout<<ma;
return 0;
}