Online Stock Span

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

    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

Online Stock Span. A stock's price arrives one day at a time. Each day, return its span: how many days in a row, ending today, had a price no higher than today's.

Prices one hundred, eighty, sixty, seventy, sixty, seventy-five, eighty-five give spans one, one, one, two, one, four, six. Seventy-five reaches back four days, until eighty stops it.

The simple way keeps every price and walks back from today each time. If prices keep rising, every walk goes all the way back: n squared steps.

Instead, picture each day as a nesting doll as tall as its price, carrying its span. Keep a shelf of dolls that get shorter toward the end. A new doll swallows every doll at the end that's no taller, and adds their spans to its own. Swallowed days never matter again.

In code, the shelf is a stack of price and span pairs. Start the span at one. While the top price is at most today's, pop it and add its span. Then push today's pair and return the span.

Let's run it. One hundred, eighty and sixty each get one. Seventy swallows sixty: two. The next sixty gets one. Seventy-five swallows sixty and seventy: one plus one plus two is four. Eighty-five swallows seventy-five and eighty: one plus four plus one, six.

Each price is pushed once and popped at most once, so n calls take linear time: constant per call, amortized. The stack holds up to n pairs. Daily Temperatures uses the same shrinking stack.

Swallow the shorter dolls, add their spans, push today. That's Online Stock Span.