Online Stock Span

Intuition

When a new price arrives, every recent day whose price was less than or equal to it is already summarized by the span stored on the stack, so we can collapse them in one step instead of rescanning. Pop each pair whose price is at most the new price, adding its span to a running total that starts at 1 for today. The pair now sitting on top is the first strictly higher price, which bounds the run. Push the new price paired with the accumulated span so future days can reuse it. Because each price is pushed and popped at most once, the amortized cost per call is constant.

Algorithm walkthrough

1. 1Store an empty stack of (price, span) pairs in the constructor.
2. 2On next(price), start span at 1 to count today.
3. 3While the stack is non-empty and the top pair's price is less than or equal to price, pop it and add its span to the running total.
4. 4Push the pair (price, span) so it represents this collapsed run.
5. 5Return span, which is the number of consecutive days up to and including today with price at most today's price.

Implementation

class StockSpanner:
    def __init__(self):
        self.stack = []  # list of (price, span)

    def next(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span