#901
Online Stock Span
Medium Monotonic stack with spans
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Prices arrive one per day. For each new price, return its span: the number of consecutive days up to today with price less than or equal to today's.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many consecutive days up to today had a price ≤ today's?
Why this works: smaller earlier prices can be merged into today's span forever; keep (price, span) on a stack.
Example: 100, 80, 60, 70, 60, 75, 85
spans 1, 1, 1, 2, 1, 4, 6✦Hints open one at a time
When today's price is higher than an earlier day, that earlier day will never be the "blocker" for any later day.
Keep a stack of (price, span) and merge smaller prices into today's span.
↗Approach
next(price): span = 1; while the top's price <= price, pop it and add its span. Push (price, span) and return span.
</>Solution (Java)
import java.util.*;
class StockSpanner {
private final Deque<int[]> stack = new ArrayDeque<>(); // {price, span}
public int next(int price) {
int span = 1;
while (!stack.isEmpty() && stack.peek()[0] <= price) {
span += stack.pop()[1]; // absorb smaller days
}
stack.push(new int[]{price, span});
return span;
}
}!Common mistake
Using < instead of <= — equal prices should be included in the span.
Complexity
- Time: Amortised O(1) per call.
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon