Online Stock Span
Medium · Stack & Strings · Stack · Monotonic Stack · Design · Data Stream
Problem
Design a class that receives a stock's daily prices one at a time and reports each day's span.
The span of today's price is the number of consecutive days, ending with today and going backwards, on which the price was less than or equal to today's price.
Implement StockSpanner:
- StockSpanner() creates an empty tracker.
- int next(int price) records today's price and returns today's span.
The tests call your class through drive(ops, args), which creates the object with the first operation and then calls the rest in order, collecting each return value (None for the constructor).
Examples
Input: ops = ["StockSpanner","next","next","next","next","next"], args = [[],[50],[40],[45],[60],[30]] Output: [None, 1, 1, 2, 4, 1]
45 covers itself and 40; 60 covers all four prices so far; 30 covers only itself.
Input: ops = ["StockSpanner","next","next","next"], args = [[],[10],[10],[10]] Output: [None, 1, 2, 3]
Equal prices count toward the span, so it grows each day.
Input: ops = ["StockSpanner","next","next","next","next","next","next","next"], args = [[],[100],[80],[60],[70],[60],[75],[85]] Output: [None, 1, 1, 1, 2, 1, 4, 6]
75 covers 60, 70 and 60 before it (span 4); 85 reaches back to just after 100 (span 6).
Constraints
- 1 <= price <= 10^5
- At most 10^4 calls are made to next
Approaches
- Baseline: keep every price, walk back — time O(n) per call, space O(n)
Follow-up
The same stack answers "previous greater element" for a whole array offline, and with the comparison flipped, "previous smaller element". For spans over a sliding window of the last k days, entries older than k days must also leave the bottom of the stack, which makes it a deque.
Related problems
Start free on Cariara · Coding problems · System design studio
