84. Largest Rectangle in Histogram

Information

  • Diffculty: Hard

  • Created: 2020-03-10 08:50:00

  • Last Motified: 2020-03-10 09:28:03

  • Tags: Array, Stack

Intuition

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.

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