title
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
solution
单调栈，求左边和右边第一个小于它的数，常规可以二分查找找这个数，但中间数据没用，可以用栈维护。参考
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
if not heights:
return 0
n = len(heights)
l = [0 for _ in range(n)]
r = [0 for _ in range(n)]
stack = []
for i, h in enumerate(heights):
while stack and heights[stack[-1]] >= h:
stack.pop()
l[i] = stack[-1] if stack else -1
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
h = heights[i]
while stack and heights[stack[-1]] >= h:
stack.pop()
r[i] = stack[-1] if stack else n
stack.append(i)
print(l, r)
ans = max(h * (r[i] - l[i] - 1) for i, h in enumerate(heights))
return ans