直方图中最大的矩形
题目 直方图中最大的矩形
思路分析
矩形面积不过是宽乘高
很容易可以发现 高其实是被限制着的
于是可以想到枚举每一根柱子 以它的高作为整个矩形的高 来去找最大的宽
最大的宽被什么限制住了呢？
显然是左右最近的一个小于当前高度的那根
可以对每个柱子都用一次双指针往左右去探 但显然这样很笨 浪费时间
对于这种 找左边最近的小于当前元素的位置 的模型
显然是单调栈
也如图看到了 为了避免判断边界情况 可以在最左和最右填一根高度为-1的柱子
对于找左边的最近的最小的柱子 用的直接是模板
找右边其实就从右边开始做就好了
最后可以找到每根柱子i的左边界l[i] 右边界r[i] 还有它的读入的高h[i]
面积就是r[i]-1 - l[i]+1 +1 * h[i]
用max维护即可
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;
LL h[N];
int l[N],r[N];
int s[N];
int n;
int main()
{
while(cin>>n && n){
for(int i=1;i<=n;i++){
cin>>h[i];
}
h[0]=h[n+1]=-1;
int top=0;
s[0]=0;
for(int i=1;i<=n;i++){
while(h[s[top]]>=h[i])
top--;
l[i]=s[top];
s[++top]=i;
}
top=0;
s[0]=n+1;
for(int i=n;i>=1;i--){
while(h[s[top]]>=h[i])
top--;
r[i]=s[top];
s[++top]=i;
}
LL res=0;
for(int i=1;i<=n;i++){
res=max(res,(LL)h[i]*((r[i]-1)-(l[i]+1)+1));
}
cout<<res<<endl;
}
return 0;
}
💬 评论