LEETCODE84Largest Rectangle in Histogram

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