i − left − 1. Neither smaller boundary can be included. If there is no smaller bar to the left, use left = −1.

Keep increasing heights by index. Popping a taller bar identifies its right boundary; the new stack top supplies its left boundary. We also pop equal heights: the newer copy inherits the ability to extend left, so a full-width candidate is still considered. A zero sentinel flushes every positive waiting height. Every possible rectangle has a minimum-height bar; at least one such bar gets the full relevant span when popped.

What the function promises: Heights are nonnegative, each bar has width one. Return the maximum area; an empty histogram has area zero. Input is not mutated.

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

assert largest_rectangle([2, 4, 2]) == 6
assert largest_rectangle([2, 2]) == 4
assert largest_rectangle([0, 0]) == 0
assert largest_rectangle([]) == 0

Work and storage: O(n) time and O(n) space: each bar enters and leaves once. The appended sentinel costs O(n) copied storage as well.

When to recognize it: A shorter bar tells taller waiting bars exactly where their rectangle must stop.

Check before applying it: The tallest bar alone may lose to several shorter bars. Equal heights need a consistent boundary rule.

At each row, accumulate consecutive-1 heights for each column, resetting on zero. Run this histogram algorithm for that row. This derives the standard maximal-rectangle method in O(rows × columns), instead of treating it as an unrelated trick.