901. Online Stock Span - Detailed Explanation

Problem Statement

Implement the StockSpanner class that collects daily stock price quotes and returns the stock span for each new price. The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price was less than or equal to today’s price.

You must support two operations:

• StockSpanner() Initializes the object.
• next(price): Given today’s stock price, returns the span of today’s price.

Examples

Input
["StockSpanner","next","next","next","next","next","next","next"]
[[],         [100],[80], [60], [70], [60], [75], [85]]
Output
[null,       1,     1,     1,     2,     1,     4,     6]

Explanation
Day 1: price = 100 → span = 1 (just today)
Day 2: price = 80  → span = 1 (80 ≤ 80 only today)
Day 3: price = 60  → span = 1
Day 4: price = 70  → span = 2 (70 ≥ 60, then stops at 80)
Day 5: price = 60  → span = 1
Day 6: price = 75  → span = 4 (75 ≥ 60,70,60; stops at 80)
Day 7: price = 85  → span = 6 (85 ≥ all previous up to 100; stops at 100)

Constraints

• Total calls to next ≤ 10⁵
• 1 ≤ price ≤ 10⁵

Naive Approach

For each call to next(price), scan backwards through the list of previously seen prices until you find a price greater than today’s. Count how many you visited (including today).

prices = []  # stored list of past prices
def next(price):
  count = 1
  i = len(prices) - 1
  while i >= 0 and prices[i] <= price:
    count += 1
    i -= 1
  prices.append(price)
  return count

• Time per call: O(n) in the worst case
• Space: O(n) to store all prices

This will TLE if you have many increasing prices in a row.

Optimized Approach (Monotonic Stack)

Maintain a stack of pairs (price, span) such that prices in the stack strictly decrease from bottom to top.

1. When next(price) is called:
   • Start with current_span = 1.
   • While the stack is not empty and stack.top.price ≤ price:
     • Pop (p, s) off the stack.
     • Add its span to current_span += s.
   • Push (price, current_span) onto the stack.
   • Return current_span.

This works because whenever you pop, you’re “skipping” all those days whose prices were ≤ today’s, and you’ve already stored their consecutive spans.

Why It’s Correct

• Stack invariant: each element’s price is greater than any below it.
• Spans accumulate exactly the count of consecutive lower/equal prices.

Complexity Analysis

• Time: Amortized O(1) per next call. Each price is pushed once and popped at most once ⇒ O(n) total.
• Space: O(n) for the stack in the worst case (strictly decreasing input).