#901 - Online Stock Span

MediumMonotonic Stack

Design a class StockSpanner that collects daily price quotes and returns the span of that day's stock price. The span is the maximum number of consecutive days (starting from today going backward) where the price was less than or equal to today's price.

Input	Output
Operations	Output
next(100), next(80), next(60), next(70), next(60), next(75), next(85)	[1, 1, 1, 2, 1, 4, 6]

Solution Space

Try it

/**
 * Computes the stock span for each day using a monotonic decreasing stack.
 * Each stack entry stores [price, span] — the span of that day.
 */
export class StockSpanner {
  private stack: [number, number][] = []; // [price, span]

  next(price: number): number {
    let span = 1;

    // Absorb all previous days with price <= current price
    while (
      this.stack.length > 0 &&
      this.stack[this.stack.length - 1][0] <= price
    ) {
      span += this.stack.pop()![1];
    }

    this.stack.push([price, span]);
    return span;
  }
}

Approach: monotonic decreasing stack of `[price, span]` pairs – on each `next(price)`, pop all entries with price ≤ current, accumulating their spans. Push the new entry with the total span.

Time: O(1) amortized per call – each entry is pushed and popped at most once across all calls.

Space: O(n) – stack stores up to n entries across all calls.

#739 Daily Temperatures

No next problem