Largest Rectangle in Histogram

An array of bar heights; find the largest rectangle that can be drawn inside the bars. A rectangle's height is capped by the shortest bar it spans, so the answer is some bar's height times the width of its "dominance region."

The key insight: for each bar, the widest rectangle at its height extends from the previous strictly-smaller bar to the next strictly-smaller bar. A monotonic increasing stack finds those boundaries in one pass. The machine pushes indices while heights are strictly increasing; when a bar is shorter than the top, that top bar's right boundary has arrived, so it pops and computes height * (i - left_boundary - 1). A sentinel height of 0 flushes the stack at the end.

Approach in steps:

1. Append a 0 sentinel to force the final flush.
2. For each index, pop while heights[stack[-1]] > heights[i]; for each pop compute the area.
3. Track the maximum area.

def largestRectangleArea(heights):
    heights.append(0)
    stack = []
    best = 0
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

Time is O(n), space O(n).

Trickiest edge case: the last bar. Without the sentinel, a monotonically increasing tail like [2,4] would never pop, and the machine would return 0 instead of 4. Equal heights need care too: using >= instead of > computes correct areas but pops duplicates early; with > every equal bar still gets measured when the next lower bar arrives.