901. Online Stock Span

On LeetCode ->

class StockSpanner:
    def __init__(self):
        pass

    def next(self, price: int) -> int:
        pass

Problem¶

Implement StockSpanner.next(price) to return the number of consecutive days ending today whose prices are at most today's price. Preserve state between calls.

Prices:  [100, 80, 60, 70, 60, 75, 85]
Spans:   [  1,  1,  1,  2,  1,  4,  6]

Key trick¶

Maintain a decreasing stack of (price, span) pairs; merge all top entries whose prices are at most today's price.

Trap¶

Include today and equal prices. One call can take \(O(n)\); only the amortized cost per call is \(O(1)\).

Why is it interesting?¶

Each price is pushed once and popped at most once, turning repeated backward scans into linear total work.

Python solution¶

class StockSpanner:
    def __init__(self):
        # Each entry summarizes a block; prices strictly decrease.
        self.stack = [] # (price, span)

    def next(self, price: int) -> int:
        span = 1  # Today always counts.

        while self.stack and self.stack[-1][0] <= price:
            _, cnt = self.stack.pop()
            span += cnt

        self.stack.append((price, span))
        return span

Time: \(O(1)\) amortized per call, \(O(n)\) total for \(n\) calls. Space: \(O(n)\).

Comment on my solution¶

Your solution is correct, including its span jumps and handling of equal prices.

It also achieves \(O(1)\) amortized time: once an entry is absorbed into a later span, future traversals skip it.
Your stack stores every day's entry rather than maintaining a decreasing stack; popping removes obsolete entries, though both have \(O(n)\) worst-case space.
The empty-stack special case is unnecessary: initializing span = 1 already handles the first call.

# Ideas:
# - Brute force with O(n) for next is easy
# - How to get O(1) or O(1) amortized?
#   - as we just want the span for the new price,
#     maybe a heap would work
#     - bad idea
# - span are consecutive days
# - maybe append in a stack both (price, span)
#   - so that we can jump backward by span gaps when price
#     is < to today's price
# - [9, 1, 7, 1, 2, 6, 8, 1, 2]
#   - [(9,0), (7,2), ...]

# WORKS
class StockSpanner:
    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        if not self.stack:
            self.stack = [(price, 1)] # (price, span)
            return 1
        i = len(self.stack) - 1
        span = 1
        while i >= 0 and self.stack[i][0] <= price:
            span_i = self.stack[i][1]
            i -= span_i
            span += span_i
        self.stack.append((price, span))
        return span