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
heights.append(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])
stack.append(i)
return largest``````

https://leetcode.com/problems/largest-rectangle-in-histogram/#/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 heights = `[2,1,5,6,2,3]`, return `10`.