Largest Rectangle in Histogram

Problem Id: 84 Difficulty: Hard Tag: Array Tag: Stack


For each column, if the next column is bigger or equal to it, then it's not possible for it to be the last column in the largest rectangle. If next column is smaller than it, then we need to take a look at the previous columns. In any previous column, if it is decreasing, then the previous higher columns should be ignored. So here comes the solution.


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [[0, -1]]
        max_area = 0
        for index, height in enumerate(heights + [0]):
            i = index
            while stack and stack[-1][0] >= height:
                h, i = stack.pop()
                area = (index - i) * h
                max_area = max(max_area, area)
            stack.append([height, i])
        return max_area