Why it works
- The largest rectangle is as high as the lowest bar under it, and it can stretch from that bar to the first lower bar on each side. So it is enough to measure every bar once, at that full width.
- A bar is popped by the first lower bar on its right, at i. The bar under it on the stack is the first lower one on its left: the bars in between were taller and already popped. So it spans left to i − 1.
- The extra step with height 0 is lower than every bar, so no bar stays unmeasured at the end.
Complexity
Time O(n): each bar is pushed once and popped once, and each pop is measured in O(1). Memory O(n) for the stack.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗