【51Nod】1102 - 面积最大的矩形面积（单调栈）

第1行：1个数N，表示数组的长度(0 <= N <= 50000)
第2 - N + 1行：数组元素A[i]。(1 <= A[i] <= 10^9)

输出最大的矩形面积

6
2
1
5
6
2
3

10

#include <stdio.h>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int main()
{
	int n;
	scanf ("%d",&n);
	LL t;
	LL ans = 0;
	LL l;
	stack<pair<LL,LL> > s;
	while (n--)
	{
		scanf ("%lld",&t);
		l = 0;
		while (!s.empty() && t < s.top().first)		//如果出现降序则不断弹出栈顶元素
		{
			l += s.top().second;
			ans = max (ans , s.top().first * l);		//更新ans 
			s.pop();
		}
		l++;		//把自己加上 
		s.push(make_pair(t,l));
	}
	l = 0;
	while (!s.empty())		//最后再执行一次弹出操作 
	{
		l += s.top().second;
		ans = max (ans , s.top().first * l);
		s.pop();
	}
	printf ("%lld\n",ans);
	return 0;
}