6/21/2017 - 12:59 PM

84. Largest Rectangle in Histogram

  1. Largest Rectangle in Histogram
class Solution(object):
    def largestRectangleArea(self, heights):
        :type heights: List[int]
        :rtype: int
        stack = []
        largest = 0
        for i in range(len(heights)):
            # Jsut like a reverse Hanoi Tower, when we encounter a height[i]
            # 1. We pop up all the values in stack that are smaller than height[i], and compute the area for those values.
            # 2. We append height[i] to the stack.
            # Note that if k s.t. `i<k<j` in stack, then height[k] >=height[i] and height[k] >= height[j].
            while len(stack) != 0 and heights[stack[-1]] >= heights[i]:
                temp = stack[-1]
                del stack[-1]
                # for the rectangle with height heights[temp],
                # the left restriction index is stack[-1]
                # the right restriction index is i
                widthLeft = temp if len(stack) == 0 else temp-stack[-1]-1
                # Width between stack[-1]<->temp (both ends exclusive).
                widthRight = i - temp -1
                # Width between temp<->i (both ends exclusive)
                largest = max(largest, (widthLeft+widthRight+1) * heights[temp])
        return largest

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example, Given heights = [2,1,5,6,2,3], return 10.