Each bar has width 1 and a given height. Find the area of the largest rectangle that fits inside the histogram.
DSA Animator › DSA Revision › Stack › Largest Rectangle in Histogram
Remember: pop a bar when a shorter one arrives; that is when its width is known. Width runs from the new stack top to the current index. The video solves Largest Rectangle in Histogram (LeetCode 84, Hard) with the Monotonic Stack pattern from the Stack topic, and you can replay every step in the interactive Largest Rectangle in Histogram animation.
Each bar has width 1 and a given height. Find the area of the largest rectangle that fits inside the histogram.
For 2, 1, 5, 6, 2, 3, the largest rectangle covers the bars 5 and 6. Its height is 5 and its width is 2, so the area is 10.
Trying every pair of left and right edges is O of n squared. For each bar, we really want how far it can stretch left and right while staying the shortest.
Keep a stack of bar indexes with increasing heights. When a shorter bar arrives, the taller bars on the stack cannot stretch any further right. So pop them one by one: each popped bar is the height, and the width runs from the new top of the stack to the current index. A zero-height bar at the end flushes everything left on the stack.
Bar 2 is pushed, then bar 1 is shorter, so pop 2: area 2. Push 1, 5 and 6, which keep increasing. Bar 2 at index 4 is shorter: pop 6, width 1, area 6. Then pop 5: the width is 2, so the area is 10, the new best. Push 2 and 3, then the final 0 pops everything. That gives areas 3, 8 and 6, none bigger than 10. The answer is 10.
In code, loop i up to n, using height 0 at the end. While the current bar is shorter than the bar on top of the stack, pop it. Its width is i if the stack is now empty, otherwise i minus the new top minus 1. Update the best area, then push i, so it's O of n time and O of n space.
Remember: pop a bar when a shorter one arrives; that is when its width is known. Width runs from the new stack top to the current index.