Online Stock Span — Monotonic Stack with Accumulated Span

Problem 264 · Online Stock Span

Difficulty: Medium · Pattern: Monotonic Stack + Span Accumulation

Span = number of consecutive days (including today) where price was ≤ today's price.

Solutions

# Python
class StockSpanner:
    def __init__(self): self.stack = []  # (price, span)
    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

// Java
class StockSpanner {
    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];
        stack.push(new int[]{price, span});
        return span;
    }
}

// C++
class StockSpanner {
    stack<pair<int,int>> st;
public:
    int next(int price) {
        int span = 1;
        while (!st.empty() && st.top().first <= price) { span+=st.top().second; st.pop(); }
        st.push({price, span});
        return span;
    }
};

Complexity

Time: O(1) amortized per call
Space: O(n)