Largest Rectangle in Histogram

def largest_rectangle(heights):
    heights = heights + [0]      # flush the stack
    stack, best = [], 0          # indices, rising
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, top * (i - left - 1))
        stack.append(i)
    return best

Largest Rectangle in Histogram. A row of bars stands side by side, each one unit wide. Find the area of the biggest rectangle that fits under them.

Take heights two, one, five, six, two, three. The best rectangle covers the five and the six: height five, width two, area ten.

The naive way tries every pair of bars. The shortest bar between them sets the height, and the distance sets the width. That's n squared pairs, too slow for a long skyline.

The trick is a stack of indices whose heights keep rising. When a shorter bar arrives, the taller bars on top can't stretch any further right. Pop each one: its rectangle reaches from the new bar back to the bar now under it on the stack.

In code, add a zero at the end to flush the stack. For each bar, while the top of the stack is taller, pop it, compute height times width, and keep the best. Then push the index.

Let's run it. Push two. One is shorter, so pop two: area two. Push one, five and six. Then two arrives: pop six, area six. Pop five, width two, area ten. Push two and three. The zero flushes the rest: three, then two times four is eight, then one times six is six. The best is ten.

Every bar is pushed once and popped once, so the time is order n. The stack can hold every bar: order n space.

Keep the heights rising, and pop when they fall. That's Largest Rectangle in Histogram.