POJ2559Largest Rectangle in a Histogram

单调栈的第一个题，看过很多遍了，最近才真的明白是什么意思

POJ2559

题意：给定n个高度不定的，宽度为1的小矩形，求可以构成的最大面积

方法：所谓单调栈，是这样一种数据结构：从栈底到栈顶是单调的

拿第一组样例来举例：

7 2 1 4 5 1 3 3

2入栈，栈的情况为：【2】

1想要入栈的时候，发现栈顶的2比自己大，把2弹出来，1进入：【1】

4进入：【4，1】

5进入：【5，4，1】

1进入的时候，5和4应该依次弹出，【1，1】

3进入，【3，1，1】

3进入，【3，3，1，1】

了解这个进栈出栈的过程，怎么去计算值呢？

看到图上标记ai的地方了吗？

如果ai可以直接插入，就是样例中的4，5这种情况

如果不行，那么每退栈一次，是需要对当前的所有面积进行计算的

再举个例子，1 3 4 5 2

在2想要进来的时候，前面已经有【5，4，3，1】在栈中

把5退出来的时候，宽度为1，可能的最大面积为5

把4退出来的时候，宽度为2，可能的最大面积为4*2=8

把3退出来的时候，宽度为3，可能的最大面积为3*3=9

然后，再把2的值插入到栈中

注意，直接插入和有元素退栈之后再插入是不同的

直接插入，说明当前的ai在栈中是最大的元素，需要记录其id号，也就是原来的位置

有元素退栈后，再插入当前元素，由于进栈入栈规则，当前元素的值会小于所有退栈元素，所以不需要更改栈顶的id号，相当于把比当前元素高的之前的元素全部变得跟当前元素一样高

如刚才的1 3 4 5 2这个例子

在2退栈的时候，由于之前id号的细节处理，计算的是（3，4，5，2）这个组的2*4=8

为了保证所有的元素都会进栈，都会出栈

定义最小的元素为第a（n+1）个元素，其高度为0即可

其余的见代码：

int n,top;
struct node{
	LL h;
	int pos;
}s[maxn];

LL a[maxn],ans,tmp;

int main(){
	input;
	while(scanf("%d",&n),n){
		ans=0;
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		a[n+1]=0;
		top=1;
		s[top].pos=1;
		s[top].h=a[1];
		for(int i=2;i<=n+1;i++)
			if (a[i]>=s[top].h){
				top++;
				s[top].pos=i;
				s[top].h=a[i];
			}
			else{
				while(a[i]<s[top].h){
					tmp=(i-1-s[top].pos+1)*s[top].h;
					if (ans<tmp) ans=tmp;
					top--;
				}
				top++;
				//s[top].pos=i;
				s[top].h=a[i];
			}
		printf("%lld\n",ans);
	}
	return 0;
}