MediumNeetCode150StackDesignMonotonic StackData Stream
Online Stock Span
Design stock span calculator.
Examples
Input
StockSpanner: next(100)=1, next(80)=1, next(60)=1, next(70)=2, next(60)=1, next(75)=4, next(85)=6
Output
1,1,1,2,1,4,6
Span: 1,1,1,2,1,4,6 days.
Constraints
- •
1 <= price <= 10^5 - •
At most 10^4 calls
Approaches
Count backwards.
CodeT: O(n^2) | S: O(n) storage
Track decreasing prices.
CodeT: O(n) total | S: O(n) stack
class StockSpanner:
def __init__(self): self.stack=[]
def next(self, price):
span=1
while self.stack and self.stack[-1][0]<=price:
span+=self.stack.pop()[1]
self.stack.append((price,span))
return spanSame approach.
CodeT: O(1) amortized | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(n) storage | Count backwards. |
| Monotonic Stack | O(n) total | O(n) stack | Track decreasing prices. |
| Monotonic Stack Optimized | O(1) amortized | O(n) | Same approach. |
Brute Force
T: O(n^2)S: O(n) storage
Count backwards.
Monotonic Stack
T: O(n) totalS: O(n) stack
Track decreasing prices.
Monotonic Stack Optimized
T: O(1) amortizedS: O(n)
Same approach.
Common Mistakes
Not using monotonic stack
Off-by-one in span count
Not amortized O(1)