84. Largest Rectangle in Histogram
这道题用stack记录递增序列，计算以某个点为高度的矩形，就要用这个点的高度乘以最右和最左的边界, 因为是递增序列，那么它的最左0或者stack[-1]，最右就是当它被pop出去时候的index-1
这题稍微tricky的地方在于在heights的右边界都加上一个值，这样保证最后一个值可以被访问到，然后stack永远不为空
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
if not heights:
return 0
if len(heights) == 1:
return heights[0]
stack = [-1]
heights = heights + [0]
max_area = 0
for i in range(len(heights)):
while heights[i] < heights[stack[-1]]:
cur = heights[stack.pop()]
max_area = max(max_area, cur*(i - stack[-1] - 1))
stack.append(i)
return max_area
