通常，直方图用于表示离散分布，例如，文本中字符的频率。 现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。 图例右图显示了所描绘直方图的最大对齐矩形。 Format Input 输入包含几个测试用例。 每个测试用例占据一行，用以描述一个直方图，并以整数 n 开始，表示组成直方图的矩形数目。 然后跟随 n 个整数 h1，…，hn。 这些数字以从左到右的顺序表示直方图的各个矩形的高度。 每个矩形的宽度为 1。 同行数字用空格隔开。 当输入用例为 n=0 时，结束输入，且该用例不用考虑。 Output 对于每一个测试用例，输出一个整数，代表指定直方图中最大矩形的区域面积。 每个数据占一行。 请注意，此矩形必须在公共基线处对齐。 数据范围 1≤n≤100000, 0≤hi≤1000000000

思路：
1. 以每个矩形为高，寻找以此矩形为高的最大矩形面积。
2. 如何寻找以此矩形为高的最大矩形面积呢？我们可以从此矩形向两边扩展，直到遇到高度小于此矩形高度的矩形，计算此时矩形的面积。
3. 如何快速寻找左右两边第一个高度小于此矩形高度的矩形呢？我们可以利用单调栈来实现。

时间复杂度：O(n)

Python代码：