[POJ2559]Largest Rectangle in a Histogram[单调栈]

题面

假如前面一段矩形高度是递增的, 现在来一个矮的矩形, 前面高出的那一截由于这个矮矩形对后面就没有贡献了, 我们只需要知道它们的宽度. 所以可以建立一个高度单调递增的单调栈, 如果新进来的矩形不满足单调, 就把比它高的矩形都弹出, 弹出的同时他们的宽度累加到新的矩形中, 同时计算被弹掉的矩形在新矩形进来之前的最大贡献(高×已累计的宽度)即可.

#include<cstdio>
#define in inline
#define re register
#define int long long
in int read()
{
	int s(0),b(0);char ch;
	do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	if(b) return -s;
	return s;
}
struct node{int w,h;node(){w=h=0;}};
struct STA{
	node sta[100001];int t;
	STA(){t=0;}
	in void push(node x){sta[++t]=x;}
	in void pop(){--t;}
	in node top(){return sta[t];}
}sta;		
int n;
signed main()
{
	while(1)
	{
		n=read();
		if(!n) break;
		int ans=0;
		for(re int i=1;i<=n+1;++i)
		{
			node x;
			if(i<=n) x.h=read();
			else x.h=0;
			while(x.h<sta.top().h&&sta.t)
			{
				x.w+=sta.top().w;
				if(x.w*sta.top().h>ans) ans=x.w*sta.top().h;
				sta.pop();
			}
			x.w+=1;//还要加上新矩形自己的宽度, 但不参与前面矩形贡献的计算.
			sta.push(x);
		}
		printf("%lld\n",ans);
		sta.t=0;
	}
	return 0;
}
赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址