class Solution(object):
def largestRectangleArea(self, height):
"""
:type heights: List[int]
:rtype: int
"""
height.append(0)
stack = [-1]
ans = 0
for i in xrange(len(height)):
while height[i] < height[stack[-1]]:
h = height[stack.pop()]
w = i - stack[-1] - 1
ans = max(ans, h * w)
stack.append(i)
height.pop()
return ans
