• 1 <= heights.length <= 10⁵
• 0 <= heights[i] <= 10⁴

Any rectangle you draw inside the histogram is capped by its shortest bar — its height can't exceed the smallest bar it spans. That suggests turning the question inside out: for each bar, ask what's the widest rectangle in which this bar is the shortest one? Such a rectangle stretches left until it hits a strictly shorter bar, and right until it hits a strictly shorter bar; between those two walls, this bar's height holds all the way across. Its area is height × (right_wall − left_wall − 1). The answer is the best of these over every bar.

The brute force finds each bar's walls by scanning outward from it, which is O(N²):

max_area = 0
n = len(heights)
for i in range(n):
    min_h = heights[i]
    for j in range(i, n):
        min_h = min(min_h, heights[j])
        max_area = max(max_area, min_h * (j - i + 1))
return max_area

The rescan is the waste, and it has a fixable shape: what we really need is, for every bar, the nearest shorter bar on each side — a "nearest smaller neighbor" query. That's the signature of a monotonic stack: a plain push/pop stack whose contents we deliberately keep sorted, so the geometry falls out in one pass.

Keep on the stack the indices of bars whose right wall we haven't found yet, and keep their heights increasing from bottom to top. Walk left to right. When the current bar is shorter than the bar on top of the stack, the current bar is that top bar's right wall — so we can finalize the top bar now: pop it, its height is heights[popped], and its left wall is whatever index is now on top (guaranteed to be the nearest shorter bar to its left, precisely because the stack rises). The width is current − new_top − 1. Keep popping while the current bar undercuts the new top — one short bar can close out a whole run of taller bars stacked above it — then push the current index.

Two sentinels keep the edges clean: seed the stack with a virtual index -1 as a permanent left wall, and append a height-0 bar at the end so every real bar still on the stack gets forced off and measured before we finish.

# Monotonic Stack (O(N) Time, O(N) Space)
heights.append(0)          # sentinel to flush every remaining bar
stack = [-1]               # sentinel left wall
max_area = 0

for i in range(len(heights)):
    while len(stack) > 1 and heights[i] < heights[stack[-1]]:
        h = heights[stack.pop()]     # this bar's right wall is bar i
        w = i - stack[-1] - 1        # left wall is the new top of the stack
        max_area = max(max_area, h * w)
    stack.append(i)

return max_area

Every bar is pushed once and popped once, so the nested-looking loop is still a single linear scan.