Design a StockSpanner class that receives a stock price every day through next(price) and returns that day's span: the number of consecutive days, ending today and going backwards, on which the price was less than or equal to today's price. Today always counts, so the span is at least 1.
- 1 <= price <= 10^5
- At most 10^4 calls to next
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force stores every price and walks back from today until a bigger price appears: O(n) per call, O(n^2) overall. When today's price is at least a previous day's price, today's span swallows that day's whole span, so those days never need to be checked one by one again. A monotonic stack of (price, span) captures this: pop every pair with a smaller or equal price, add up their spans, and push today's combined pair. Each pair is pushed and popped once, so calls are O(1) amortised.
Algorithm
- Keep a stack of
(price, span)pairs; prices strictly decrease from bottom to top. - In
next(price), start withspan = 1. - While the stack is not empty and the top price is
<= price, pop it and add its span. - Push
(price, span)and returnspan.
O(1) amortised per callSpace: O(n)<= when popping, not <: equal prices are part of the span. This is the "previous greater element" pattern, the mirror image of Daily Temperatures.class StockSpanner: def __init__(self): # Each entry is (price, span); prices strictly decrease from bottom to top. self.stack = []Β def next(self, price: int) -> int: span = 1 # today while self.stack and self.stack[-1][0] <= price: span += self.stack.pop()[1] # absorb the earlier day's whole span self.stack.append((price, span)) return span