LeetCode 84 Largest Rectangle in Histogram - Example and Complexity Analysis

Trace [2, 1, 5, 6, 2, 3, 0] (added sentinel).

i=0 (h=2): push 0. Stack: [0].

i=1 (h=1): 1 < 2, pop 0. Width = 1 - (-1) - 1 = 1. Area = 2×1 = 2. Push 1. Stack: [1].

i=2 (h=5): push 2. Stack: [1, 2].

i=3 (h=6): push 3. Stack: [1, 2, 3].

i=4 (h=2): 2 < 6, pop 3. Width = 4 - 2 - 1 = 1. Area = 6×1 = 6. 2 < 5, pop 2. Width = 4 - 1 - 1 = 2. Area = 5×2 = 10. Push 4. Stack: [1, 4].

i=5 (h=3): push 5. Stack: [1, 4, 5].

i=6 (h=0): pop 5, 4, 1. Best area from these pops. Max = 10.

Each bar pushed once, popped once. $O(n)$ time. $O(n)$ space.