Why it works
- A popped pair is not higher than today, and neither are the days it stands for: they were all at most its price. So today’s span takes in all of them at once.
- Pairs on the stack rise towards the bottom: a pair that was not higher would have been popped. The first higher pair ends the span, and nothing under it can be reached.
- A popped day is never needed again: today is at least as high and comes later, so any later day either stops at today or goes past both.
Complexity
Each next is O(1) on average: every price is pushed once and popped at most once, so n calls do at most 2n stack steps in all. Memory O(n) for the stack.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗