Monotonic Stack — Online Stock Span
↗ LeetCode: Online Stock Span · Medium · pattern chapter →
Design StockSpanner. Method next(price) returns the span of the current day — the max number of consecutive days (going back and including today) where the price was less than or equal to today's.
Example 1 —
StockSpanner S = new StockSpanner();
S.next(100); // 1
S.next(80); // 1
S.next(60); // 1
S.next(70); // 2 (70 > 60)
S.next(60); // 1
S.next(75); // 4 (75 > 60,70,60)
S.next(85); // 6Example 2 — Monotonic decrease: S.next(100); next(90); next(80) → returns 1, 1, 1. Example 3 — Monotonic increase: S.next(1); next(2); next(3); next(4) → returns 1, 2, 3, 4.
Constraints — 1 ≤ price ≤ 10⁵; up to 10⁴ calls. Naive per-call scan is O(n) each — worst-case O(n²) = 10⁸ across 10⁴ calls. Monotonic stack is amortized O(1) per call = 10⁴ ops total.
Interview timer00:00
Approach 1 — Store all prices, scan on each next
Intuition. Keep list of all prices; on each call, walk backward counting.
Complexity — Time O(n) per next, O(n²) worst total; Space O(n).
Approach 2 — Monotonic decreasing stack (canonical)
Insight from brute. Each incoming price collapses a run of smaller-or-equal older prices — those older prices can never contribute to a future span (this bigger price sits between them and the future). Store (price, span) pairs on a stack; on next(p), pop everything ≤ p, sum spans, push (p, totalSpan).
Why amortized O(1). Each price is pushed once and popped at most once — total work is O(N) across N calls.
class StockSpanner {
Deque<int[]> stack = new ArrayDeque<>();
public int next(int price) {
int span = 1;
while (!stack.isEmpty() && stack.peek()[0] <= price) span += stack.pop()[1];
stack.push(new int[]{price, span});
return span;
}
}Complexity — Amortized O(1) per next; Space O(n) worst.
Try it yourself
Complexity summary
| Approach | Time per next | Space | Interview grade |
|---|---|---|---|
| Store and scan | O(n) | O(n) | baseline |
Monotonic stack (price, span) | O(1) amortized | O(n) | canonical |
When to use which
- Streaming NGE / span → monotonic stack with span-accumulation.
- "Return the actual indices, not span" → push (price, index); span = current - stack.peek().index.
- Offline max — no streaming → non-streaming variant is Daily Temperatures.
- "Span with equality reversed (strictly less)" → change the pop condition to
< price.
Related problems
- Daily Temperatures
- Next Greater Element II — circular sibling
- Sliding Window Maximum — deque-based sibling