Every bar wants to be the shortest bar in a rectangle. The monotonic stack waits until a shorter bar arrives — then it finally knows exactly how far that rectangle could stretch.
When a shorter bar arrives, cash out.
Scan left to right and keep indices whose heights are increasing. While the new bar is at least as tall as the stack top, the older bars can still stretch right. The instant a shorter bar appears, those taller bars are finished — so measure them and move on.
Start with the classic [2, 1, 5, 6, 2, 3]. Step slowly, then replay at speed once the invariant clicks.
0 at the end so every remaining bar gets popped.def largestRectangleArea(heights):
stack = [] # increasing heights' indices
best = 0
# sentinel 0 flushes the stack at the end
for i, h in enumerate(heights + [0]):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] if stack else -1
width = i - left - 1
best = max(best, height * width)
stack.append(i)
return bestThe sentinel index is pushed after the final flush. It is only a control value; it is not part of the histogram.
iThe first index with a smaller height — the bar that triggered the pop.stack[-1] + 1Just after the next smaller bar on the left (the new stack top).i - stack[-1] - 1Fallout of storing indices, not just heights.When the second 2 arrives, pop 6 (width 1 → 6), then pop 5 (width 2 → 10). The bar of height 5 stretches across indices 2–3.
The sentinel 0 arrives after the scan: pop 4 with width 1, then pop 2 with width 2. The final flush is not an edge-case patch — it is the same right-boundary logic.
“I maintain indices of increasing heights. When I see a smaller height, each popped bar has found its first smaller element on the right. The remaining stack top is its first smaller element on the left, so I know its exact maximal width. Each index is pushed and popped once, giving linear time.”