AcWing 131. 直方图中最大的矩形 带注释
原题链接
简单
作者:
蓬蒿人
,
2021-05-20 22:03:25
,
所有人可见
,
阅读 252
#include <iostream>
using namespace std;
typedef long long LL; // x
//仔细观察可以发现直方图中的每个包含柱子i的矩形 xx
//都会被 左边第一个比他矮和右边第一个比他矮的柱子卡住 00xxx000
//由此 我们就可以遍历包含柱子i的矩形得到最大矩形
//矩形的面积为(右边卡住的柱子r-左边l)*高度h【i】
//而卡住柱子的下标的求法 就是利用单调栈求左右两边第一个比i小的数
int n,h[100010],l[100010],r[100010],q[100010],tt;
//l数组存卡组i的左边柱子的下标 r是右边 q是模拟栈的数组 从0开始存数
int main (){
while (cin>>n,n){
for (int i=1;i<=n;i++ ) scanf ("%d",&h[i]);
h[0]=h[n+1]=-1;
//为了避免处理边界问题 将左右边界高度设为-1
q[0]=0;
tt=0;
for (int i=1;i<=n;i++){
while (tt>0&&h[i]<=h[q[tt]]) tt--;
l[i]=q[tt];
q[++tt]=i;
}
//单调栈模板
tt=0,q[0]=n+1;
//这里注意 tt归0 q的栈顶元素应为n+1
for (int i=n;i;i--){
while (tt>0&&h[i]<=h[q[tt]]) tt--;
r[i]=q[tt];
q[++tt]=i;
}
long long res=0;
for (int i=1;i<=n;i++) res=max(res,(long long)(r[i]-l[i]-1)*h[i]);
//注意long long和-1
cout<<res<<'\n';
}
return 0;
}