HDU OJ 1506 Largest Rectangle in a Histogram 和 NYOJ 258 最大长方形 [单调队列]

思路：单调队列，开两个数组 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<stdio.h>
#include<string.h>
#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<n)
                scanf("%d",&h);
            else
                h=-1;
            if(top<0||stack[top]<h)
            {
                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

补充：软件开发 , C++ ,