Largest Rectangle in Histogram

Question Description

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 height = [2,1,5,6,2,3], return 10.

Solution

There is a very subtle stack solution for this question.

  1. Initialize a empty stack.
  2. If stack is empty or the current height is bigger than the one at the top of stack, we push the index into the stack.
  3. If not in (2), we pop the elements in stack out and compute the rectangle area formed by every popped element until the top element is smaller than the current one.

Here because the remaining element in stack should always be increasing order, the popped element should be the smallest if the stack is empty. (i - stk[-1] - 1 or i)

And we could also push a zero at the end of array, in that case we can avoid dealing with the last index.

Detailed analysis is from this blog.

class Solution(object):
    def largestRectangleArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        stk, i, result = [], 0, 0
        height.append(0)
        while i < len(height):
            if len(stk) > 0 and height[i] < height[stk[-1]]:
                t = stk.pop()
                if len(stk) == 0:
                    result = max(result, i * height[t])
                else:
                    result = max(result, (i - stk[-1] - 1) * height[t])
            else:
                stk.append(i)
                i += 1
        return result

Maximal Rectangle