卢俊达

题目大意：

给出一个整数n，表示有n个宽为1的矩形。紧接着输入n个整数，表示每个矩形的高，要求输出最大连续矩形的面积。

思路：

单调栈。

代码：

#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
struct point
//将矩形的高度和位置封装在结构体中。 
{
	int val;
	//矩形高度的值。 
	int pos;
	//pos表示矩形在序列中的位置。 
}height[100001];
int main()
{
	int n;
	while(scanf("%d",&n)&&n)
	{
		stack<point> s;
		for(int i=0;i<n;i++)
		{
			scanf("%d",&height[i].val);
			height[i].pos=i;
		}
		height[n].val=0;
		height[n].pos=n;
		//使用height[n]的目的是使下面的循环可以在单调递增序列下正常求取面积。 
		s.push(height[0]);
		long long max=0;
		for(int i=1;i<=n;i++)
		{
			while(s.size()&&height[i].val<=s.top().val)
			//在栈不为空的情况下，判断当前矩形的高是否小于等于栈顶矩形的高。 
			{
				long long area=(long long)s.top().val*(long long)(i-s.top().pos);
				max=max>area?max:area;
				height[i].pos=s.top().pos;
				//这一步很微妙，要了解单调栈在本题中的几何意义。
				//循环里的这几步操作实际上相当于将矩形i重新放置到左边第一个比它小的矩形前， 
				//并计算矩形i右边第一个矩形到循环开始前的栈顶矩形的最大连续面积。
				//而对矩形i的放置操作就体现在了对height[i].pos的更改上。 
				s.pop();
			}
			s.push(height[i]);
		}
		printf("%I64d\n",max);
	}
}