Leetcode 84. Largest Rectangle in Histogram

Seawolf

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:

Input: [2,1,5,6,2,3]
Output: 10

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        if heights == None or len(heights) == 0:
            return 0
        res = 0
        stack = []
        for i in range(len(heights) + 1):
            if i == len(heights):
                curt = -1
            else:
                curt = heights[i]
            while stack and curt <= heights[stack[-1]]:
                h = heights[stack.pop()]
                if len(stack) != 0:
                    w = i - stack[-1] - 1
                else:
                    w = i
                res = max(res, w * h)
            stack.append(i)
        return res