Each value is the height of a bar. The largest rectangle under the histogram is bounded by the nearest shorter bar on each side of some bar. Scan left to right keeping a stack of bars with rising heights: when a lower bar arrives, every taller bar on the stack has found its right bound, and the bar below it on the stack is its left bound. A sentinel of height 0 at the end flushes the stack.
Largest rectangle in a histogram of 6 bars.
Push bar 0 of height 2: the stack was empty.
Push bar 0.
Bar 1 has height 1, not taller than the top of the stack, 2 at index 0. Pop it: its rectangle reaches right to index 0 and left to index 0 (no shorter bar on the left), width 1, area 2 x 1 = 2. New best.
Pop bar 0 of height 2: area 2.
Push bar 1 of height 1: the stack was empty.
Push bar 1.
Push bar 2 of height 5: it is taller than 1 below it, so the stack still rises.
Push bar 2.
Push bar 3 of height 6: it is taller than 5 below it, so the stack still rises.
Push bar 3.
Bar 4 has height 2, not taller than the top of the stack, 6 at index 3. Pop it: its rectangle reaches right to index 3 and left to index 3, just past the shorter bar 2, width 1, area 6 x 1 = 6. New best.
Pop bar 3 of height 6: area 6.
Bar 4 has height 2, not taller than the top of the stack, 5 at index 2. Pop it: its rectangle reaches right to index 3 and left to index 2, just past the shorter bar 1, width 2, area 5 x 2 = 10. New best.
Pop bar 2 of height 5: area 10.
Push bar 4 of height 2: it is taller than 1 below it, so the stack still rises.
Push bar 4.
Push bar 5 of height 3: it is taller than 2 below it, so the stack still rises.
Push bar 5.
The sentinel of height 0 flushes the stack: top is 3 at index 5. Pop it: its rectangle reaches right to index 5 and left to index 5, just past the shorter bar 4, width 1, area 3 x 1 = 3. Best stays 10.
Pop bar 5 of height 3: area 3.
The sentinel of height 0 flushes the stack: top is 2 at index 4. Pop it: its rectangle reaches right to index 5 and left to index 2, just past the shorter bar 1, width 4, area 2 x 4 = 8. Best stays 10.
Pop bar 4 of height 2: area 8.
The sentinel of height 0 flushes the stack: top is 1 at index 1. Pop it: its rectangle reaches right to index 5 and left to index 0 (no shorter bar on the left), width 6, area 1 x 6 = 6. Best stays 10.
Pop bar 1 of height 1: area 6.
Largest rectangle: area 10 over indices 2 to 3. Every bar is pushed once and popped once, 6 pops in all, so the scan is O(n) although each bar's rectangle can span the whole array.
Largest rectangle has area 10.