LC84. Largest Rectangle in Histogram

Approach 1: Brute Force

TODO

Approach 2: Binary Search

TODO

Approach 3: Stack

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        n = len(heights)
        maxArea = 0
 
        for i, currHeight in enumerate(heights):
            start = i
            while stack and currHeight < stack[-1][1]:
                prevIdx, prevHeight = stack.pop()
                maxArea = max(maxArea, (i - prevIdx) * prevHeight)
                start = prevIdx
            
            stack.append((start, currHeight))
        
        while stack:
            prevIdx, prevHeight = stack.pop()
            maxArea = max(maxArea, (n - prevIdx) * prevHeight)
        
        return maxArea

Complexity

Time: $O(n)$
Space: $O(n)$

Notes

Other Languages