Largest Rectangle in Histogram

Intuition

For every bar, the biggest rectangle capped at that bar's height extends left and right until it meets a strictly shorter bar. A stack of indices whose heights are increasing lets us discover those boundaries efficiently. When the incoming bar is shorter than the bar on top of the stack, the incoming index is the right boundary for the popped bar, and the new top of the stack (after popping) is its left boundary. Compute the area with the popped height and that width. Appending a sentinel bar of height 0 forces every remaining bar to be flushed and measured.

Algorithm walkthrough

1. 1Initialize an empty stack of indices and a running best area of 0.
2. 2Scan i from 0 through the array, treating an index just past the end as a bar of height 0 (the sentinel).
3. 3While the stack is non-empty and the current height is less than the height at the top index, pop that top as the limiting height h.
4. 4The width is i minus the index of the new top minus one (or i itself when the stack becomes empty), so area = h * width; update the best area.
5. 5Push the current index and continue; after the sentinel is processed the stack is empty and the best area is the answer.

Implementation

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []
        best = 0
        n = len(heights)
        for i in range(n + 1):
            cur = heights[i] if i < n else 0
            while stack and cur < heights[stack[-1]]:
                h = heights[stack.pop()]
                left = stack[-1] if stack else -1
                width = i - left - 1
                best = max(best, h * width)
            stack.append(i)
        return best