visual walkthrough
Online Stock Span
Previous-greater spans in a streaming (online) setting.
The idea
The span ends at the first earlier day with a higher price. A stack of (price, span) pairs remembers, for each surviving price, how many days it already covers.
A new price pops every smaller-or-equal price and adds their spans, so no day is ever re-examined.
Complexity
| approach | time | space |
|---|---|---|
| Look back each day | O(n²) | O(1) |
| Monotonic stack | O(n) | O(n) |