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
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 =
The largest rectangle is shown in the shaded area, which has area =
Given heights =