Largest Rectangle in Histogram

Problem: Largest Rectangle in Histogram

We can use a stack to maintain all the histograms. When we get a new histogram, it may be higher than the toppings of stack or shorter. If it's smaller, there's no need to maintain higher histograms in the stack since we will no longer use that height to construct rectangle.

We can add a minimum to stack first so that we can maintain left most position in the stack and we can add 0 to the stack so that we will always pop all heights.

Code in Python:

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