Online Stock Span

Share

Design a system collecting stock prices daily. stockSpan() returns number of consecutive days (including today) price was <= today's price.

Example 1
Input: SpanningSystem.next() with [100,80,60,70,60,75,85] → Output: [1,1,1,2,1,4,6]
Example 2
Input: → Output:

Solution Approach

Monotonic stack: store (price, span) pairs. Pop smaller prices and accumulate spans.

  • Stack of (price, span) pairs
  • For each new price: span = 1
  • While stack top price <= current: span += top.span, pop
  • Push (price, span)
  • Return span
Java
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;
    }
}
  • Time Complexity: O(1) amortized
  • Space Complexity: O(n)