HDU OJ 1506 Largest Rectangle in a HistogramとNYOJ 258最大長方形(二)【単調キュー】

原題接続: http://acm.hdu.edu.cn/showproblem.php?pid=1506  (hdu)
考え方:単調なキュー、2つの配列stack[]とlenを開く [ ]  stack[]メモリ入力の長len[ ] 存宽.stack里按单增存,遇到比stack[top]小的データ就要说顶部元素删除,至于删除后顶部可存,在删除之前要看更新ans((l+len[top])*stack[top]与现在ans取最大值给ans) 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);
			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
",ans);
	}
}