EACH BAR'S BIGGEST RECTANGLE REACHES OUT UNTIL IT MEETS A SHORTER BAR. KEEP A STACK OF BARS WHOSE HEIGHTS ONLY RISE. WHEN A SHORTER BAR ARRIVES, EVERY TALLER BAR HAS FOUND ITS RIGHT EDGE, SO POP AND MEASURE EACH. A PHANTOM END WALL OF HEIGHT 0 FLUSHES THE REST, AND EACH BAR IS PUSHED AND POPPED ONCE, SO O(N).

BLUE IS THE CURRENT BAR. TAN BARS WAIT ON THE STACK, A RISING RUN. A GREEN BAR IS POPPED THIS STEP, ITS ARC AND READOUT SHOWING WIDTH TIMES HEIGHT. GOLD MARKS A NEW BEST. THE GHOSTED END WALL IS A HEIGHT 0 SENTINEL THAT FLUSHES THE STACK.

1def largest_rectangle_area(heights):2    stack = []3    max_area = 04    for i in range(len(heights) + 1):5        while stack and (i == len(heights) or heights[stack[-1]] > heights[i]):6            j = stack.pop()7            width = i if not stack else (i - stack[-1] - 1)8            max_area = max(max_area, width * heights[j])9        stack.append(i)10    return max_area