首页 > 代码库 > 【单调栈】hdu1506 Largest Rectangle in a Histogram
【单调栈】hdu1506 Largest Rectangle in a Histogram
单调栈的介绍及一些基本性质
http://blog.csdn.net/liujian20150808/article/details/50752861
依次把矩形塞进单调栈，保持其单增，矩形中的元素是一个三元组，存储其位置，高度，以及以其为高度的情况下，大矩形的左边界最多扩展到哪里。
每次将新的元素塞进栈的时候，其左边界就是其左侧第一个小于它的矩形的位置+1。
然后，每个矩形出栈的时候，记录其右边界为当前往栈里面塞的矩形的位置-1，然后更新答案即可。
注意最后把所有的矩形出栈，更新答案。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long ll;
struct data
{
int l,h,p;
data(const int &X,const int &Y,const int &Z)
{
l=X;
h=Y;
p=Z;
}
data(){}
};
stack<data>st;
int n,a[100010];
ll ans;
int main()
{
while(1)
{
scanf("%d",&n);
if(!n)
break;
ans=0;
st.push(data(0,-1,0));
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
a[n+1]=-1;
for(int i=1;i<=n+1;++i)
{
while((!st.empty()) && a[i]<=st.top().h)
{
ans=max(ans,(ll)(i-st.top().l)*(ll)st.top().h);
st.pop();
}
if(!st.empty())
st.push(data(st.top().p+1,a[i],i));
}
cout<<ans<<endl;
}
return 0;
}
【单调栈】hdu1506 Largest Rectangle in a Histogram
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。