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