题目描述

直方图是由在公共基线处对齐的一系列矩形组成的多边形。
矩形具有相等的宽度，但可以具有不同的高度。
例如，图例左侧显示了由高度为 2, 1, 4, 5, 1, 3, 3 的矩形组成的直方图，矩形的宽度都为 1：
 

通常，直方图用于表示离散分布，例如，文本中字符的频率。
现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。
图例右图显示了所描绘直方图的最大对齐矩形。

输入格式

输入包含几个测试用例。
每个测试用例占据一行，用以描述一个直方图，并以整数 n 开始，表示组成直方图的矩形数目。
然后跟随 n 个整数 h1, …, hn。
这些数字以从左到右的顺序表示直方图的各个矩形的高度。
每个矩形的宽度为 1。
同行数字用空格隔开。
当输入用例为 n=0 时，结束输入，且该用例不用考虑。

输出格式

对于每一个测试用例，输出一个整数，代表指定直方图中最大矩形的区域面积。
每个数据占一行。
请注意，此矩形必须在公共基线处对齐。

数据规模

1≤n≤100,000；
0≤hi≤1,000,000,000。

输入样例

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

输出样例

8
4000

注释版代码

#include<iostream>
using namespace std;
const int N=100010;
int q[N],h[N],l[N],r[N];//q[]代表一个单调栈，里面存储的是数组h中柱子的索引，这些柱子满足；
//栈顶元素对应的柱子是当前柱子能看到的最左边且高度小于当前柱子
//栈里面的索引对应的柱子是从左到右递增的
typedef long long LL;
int main()
{
	int n;
	while(cin>>n,n)//while返回最后一个表达式的值
	{
		for(int i=1;i<=n;i++) cin>>h[i];
		h[0]=h[n+1]=-1;
		int tt=0;
		q[0]=0;//从左边进行遍历左边边界
		for(int i=1;i<=n;i++)
		{
			while(h[i]<=h[q[tt]]) tt--;
			//如果当前元素小于等于栈顶元素的值的话，那往左遍历的时候，当前元素一定会卡住左边的的值（即栈内的元素）
			//所以如果当前元素小于等于栈顶元素的话，其实栈顶的元素就没有用了，这时需要把栈顶元素出栈
			l[i]=q[tt];//那么此时的栈顶元素就是能到达的左边最远边界
			q[++tt]=i;//然后把当前元素插入到栈
		}
		tt=0;
		q[0]=n+1;//从右边进行遍历进行右边边界
		for(int i=n;i>0;i--)
		{
			while(h[i]<=h[q[tt]]) tt--;
			r[i]=q[tt];
			q[++tt]=i;
		}
		LL res=0;
		for(int i=1;i<=n;i++)
		{
			res=max(res,(LL)h[i]*(r[i]-l[i]-1));
		}
		printf("%lld\n",res);
	}
	return 0;
}