Online Stock Span
Each day a price arrives; return its span — how many consecutive days ending today had price ≤ today's.
Open on LeetCode ↗02
Intuition
A price swallows the spans of every smaller-or-equal price before it. Keep a stack of (price, span) pairs with strictly decreasing prices: a new price pops and absorbs what it dominates, then pushes its accumulated span.
03
Approach
1
Spans compress history
Once a day is inside some later day's span, it can never matter individually again — safe to merge and discard.
2
Pop while ≤
New price p starts with span 1, adds the span of every popped pair with price ≤ p, then pushes (p, span).
3
Amortized O(1) per day
Each pair pushed once, popped at most once — n calls cost O(n) total.
04
Solution & live demo
python
▶1class StockSpanner:
▶2 def __init__(self):
▶3 self.stack = [] # (price, span), prices decreasing
▶4
▶5 def next(self, price):
▶6 span = 1
▶7 while self.stack and self.stack[-1][0] <= price:
▶8 span += self.stack.pop()[1]
▶9 self.stack.append((price, span))
▶10 return span
05
Edge cases
Strictly increasing prices
Every new price pops everything — spans grow like 1,2,3…
Equal prices
≤ comparison absorbs equals into the new span (span counts ≤ days).
06
Complexity
Time
amortized O(1)
Space
O(n)
Each price enters/leaves the stack once.