Hard · Monotonic Increasing Stack
Understand → Visualise → Practice.
Return the largest rectangle area that can be formed from contiguous histogram bars.
Keep a stack of bars with increasing heights. When a shorter bar arrives, each taller bar on the stack can't extend further right, so compute its rectangle using the new top as its left limit.
Process the heights plus a final 0 so every bar is eventually popped.
While the top bar is taller than the current one, pop it; its width runs from just after the new top to i − 1.
Area = height × width; keep the maximum, then push i.
O(n) time and O(n) space.
Forgetting the final sentinel leaves bars on the stack whose areas are never computed.
Read the full guides first: Stacks, Queues and Deques.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.