求数组与下标所能够构成最大面积

leetcode84 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。

思路：初始化一个栈stack，遍历数组arr。当当前值大于等于栈顶元素则将当前元素入栈；当当前值小于栈顶元素时，当前位置为当前矩形的右边界，栈顶元素出栈即为当前矩形的高度，新的栈顶元素的位置的下一个位置为当前矩形的左边界，计算当前矩形的面积；继续比较当前值与栈顶元素的关系，重复上面过程，即可求解柱状图的最大矩形。

考虑上述思路，记录元素位置比较方便位置计算，另当出栈到栈为空的时候，矩形的左边界为柱状图第一个元素的位置，需要特殊考虑。

代码如下：

def getMaxArea(arr):
    stack = []
    i, result = 0, 0
    while i < len(arr):
        while len(stack) > 0 and arr[stack[-1]] > arr[i]:
            h = arr[stack.pop()]
            result = max(result, h*(i-1-(-1 if len(stack) == 0 else stack[-1])))
        stack.append(i)
        i += 1
    while len(stack) > 0:
        h = arr[stack.pop()]
        result = max(result, h*(len(arr)-1-(-1 if len(stack) == 0 else stack[-1])))
    return result