312. Online Stock Span

Keep a stack of previous days that are strictly greater than everything after them. When a new price arrives, absorb (pop) all earlier days with price <= today, summing their spans — those days are now dominated by today.

Collapse dominated days

Store a stack of (price, span) pairs. For a new price:

1. Start span = 1 (today itself).
2. While the top of the stack has price <= today, pop it and add its span to today's — those consecutive earlier days are all <= today, so they extend today's span.
3. Push (price, span) and return span.

The stack stays strictly decreasing in price, so each day is pushed and popped at most once — amortised O(1) per call.

Worked example

Prices 100,80,60,70,60,75,85 → spans 1,1,1,2,1,4,6. On day of price 75, it absorbs 60(span1) and 70(span2) and 60(span1) → 1+1+2+... = span 4.

Complexity

• Time: amortised O(1) per next.
• Space: O(n).

import java.util.ArrayDeque;
import java.util.Deque;

class StockSpanner {
    private Deque<int[]> stack = new ArrayDeque<>();  // (price, span)

    public StockSpanner() {
    }

    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;
    }
}