HDU OJ 1506 Largest Rectangle in a Histogram 和 NYOJ 258 最大长方形（二） 【单调队列】
原题连接： http://acm.hdu.edu.cn/showproblem.php?pid=1506 (hdu)
思路：单调队列，开 两个数组 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代码：
/*此代码为 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);elseh=-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);}}