HDU OJ 1506 Largest Rectangle in a Histogram 和 NYOJ 258 最大长方形 [单调队列] - c++编程基础

思路：单调队列，开两个数组 stack [ ] 和 len [ ] stack [ ] 存输入的长 len [ ] 存宽。stack 里面按单增存，遇到比 stack [ top ] 小的数据就要讲顶部元素删除，直到删后顶部可以存为止，在删之前要看是否可以更新 ans （(l+len[ top ])*stack[ top ] 与当前 ans 取最大值给 ans），记下此时 len [ top ] 的值，给 l （l+=len[ top ]），新进入的 len 值即为 l +1 ，具体看代码理解。
AC代码：
[cpp]
/*此代码为 nyoj ac 代码，若在 hdu oj 要讲 long long 改为 __int64（对应输出格式也要改下），hdu oj 不支持 long long*/
#include
#include
#define max(a,b) a>b a:b
int stack[100010],len[100010];
int main()
{
int a,b,n,h;
while(scanf("%d",&n)&&n)
{
long long top=-1,ans=0;
for(a=0;a<=n;a++)
{
if(a scanf("%d",&h);
else
h=-1;
if(top<0||stack[top] {

stack[++top]=h;
len[top]=1;
}
else
{
int l=0;
while(stack[top]>=h&&top>=0)
{
ans= max(ans,(long long)(len[top]+l)*stack[top]);
l+= len[top--];
}
if(h>0)
{
stack[++top]=h;
len[top]=1+l;
}
}
}
printf("%lld\n",ans);
}
}
作者：PIAOYI0208