Largest Rectangle in Histogram

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.

Example

Given height = [2,1,5,6,2,3],

return 10.

Solution:

(1) 首先可以想到暴力法，两层循环 ， 复杂度n^3

(2) 递增栈， 递减栈, 是常用的解决找到每个数左右比他小的数。与TreeMap 异曲同工。如图上所示，维持一个递增栈不符合条件的例如，5, 6, 这个时候就需要对5,6， 从后面往前遍历，例如下面列表中，i =4, 的两种情况。

首先就是维护一个递增盏，当每次弹出不合格的盏，需要计算下宽度， 高度，面积，由于是递增盏，i - j - 1 这个面积内必定高度全部满足于curr, j + 1, j 是当前柱形图的前一个位置，i则是递减的位置，两头一减，中间的必然就是全部满足的，根据递增盏的性质。

if current = 5, so 1 less 5 and 2 less 5 so 5 * 2 = current 5 max value

the stack should always store index then real value which could be duplicate

i=1 w=1 h=2

i=4 w=1 h=6

i=4 w=2 h=5

i=6 w=1 h=3

i=6 w=4 h=2

i=6 w=6 h=1

class Solution:
    """
    @param height: A list of integer
    @return: The area of largest rectangle in the histogram
    """
    def largestRectangleArea(self, height):
        stack = []
        area = 0
        for i in range(len(height) + 1):
            curr = height[i] if i < len(height) else -1
            while stack and curr <= height[stack[-1]]:
                h = height[stack.pop()]
                w = i - stack[-1] - 1 if stack else i
                area = max(area, h * w)
            stack.append(i)
        return area