Approach Summary
Monotonic decreasing stack of (price, span) pairs. When a new price is ≥ top, pop and accumulate its span. Push new (price, accumulated span).
How to Recognize This Pattern
- "How many consecutive days price ≤ today"
- Monotonic stack accumulates spans of popped elements
Complexity Analysis
Time Complexity
O(1) amortized
Space Complexity
O(n)
Tags
Stack Design Monotonic Stack Data Stream