largest_rectangle_in_histogram.py

from typing import List


class Solution:
    """LeetCode #84 - Largest Rectangle in Histogram (Hard)
    https://leetcode.com/problems/largest-rectangle-in-histogram/

    `heights` holds the heights of unit-width bars. Return the area of the
    largest rectangle that fits entirely inside the histogram.
    """

    def largestRectangleArea(self, heights: List[int]) -> int:
        """Monotonic increasing stack of `(start_index, height)` pairs.

        Reframe the problem: every candidate rectangle is limited by some bar
        that is its shortest one. So instead of asking "which rectangle is
        biggest", ask for each bar "how far can a rectangle of *this* height
        stretch left and right before hitting something shorter?".

        The stack answers the right-hand side for free. It holds bars whose
        heights only increase, so when a shorter bar arrives every taller bar
        on the stack has just found its right boundary - the current index -
        and can be settled: `height * (i - start)`.

        The `start` field is the part people miss. A popped bar's rectangle
        also extends *backwards* over everything already popped in this step
        (all of it was taller). Carrying `start` down to the newcomer records
        that the newcomer could itself have begun back there.

        Whatever is still on the stack at the end never met a shorter bar, so
        it extends to the right edge - hence the second loop.

        Time:  O(n) - every bar is pushed once and popped at most once.
        Space: O(n) in the worst case (heights already increasing).
        """
        stack = []        # (start_index, height), heights strictly increasing
        best = 0

        for i, h in enumerate(heights):
            start = i     # how far left a bar of height h could reach

            while stack and stack[-1][1] > h:
                idx, height = stack.pop()
                best = max(best, height * (i - idx))
                start = idx     # inherit the popped bar's left reach

            stack.append((start, h))

        n = len(heights)
        for idx, height in stack:
            best = max(best, height * (n - idx))

        return best