问题1708--直方图中最大的矩形

1708: 直方图中最大的矩形

时间限制: 1 Sec  内存限制: 128 MB
提交: 39  解决: 30
[提交] [状态] [讨论版] [命题人:]

题目描述


给出n（1≤n≤100000）个宽度为1的矩形，垂直拼接于一水平线上（如下图）。告诉每个矩形的高hi（0≤hi≤1000000000），求出图形中最大的矩形面积（下图中最大面积为阴影部分，样例数据为下图数据）。


输入

有多组数据，数据由0结束。 每一行第一个数n，接下来n个hi

输出

有多行，每行为每组数据的最大面积。

样例输入 Copy 

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

样例输出 Copy 

8
4000

来源/分类

栈 单调栈 
[提交] [状态]