单调队列与单调栈
D. 求最大面积
描述
HISTOGRA-Largest Rectangle in a Histogram。如图所示，在一条水平线上有n个宽为1的矩形，问里面包含的矩形的最大面积是多少（图中的阴影部分的面积即所求答案）。
输入
有多组测试数据，每组数据占一行。输入零时读入结束。
每行开头为一个数字n(1≤n≤10^5)，接下来在同一行给出n个数字h1，h2，…，hn(0≤hi≤10^9)，表示每个矩形的高度。
输出
对于每组数据，输出最大子矩阵面积，一组数据输出一行。
样例
输入
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
输出
8 4000
Submit
登录
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |