⚡Flashcard Drill➔
NeetCode #356LC-901MediumStackNC 250
← Back to All Problems

#356 · #901 · Online Stock Span(股票价格跨度)

📌 Problem Statement & Constraints

Design a class that collects daily price quotes and returns the span of the stock price for the current day: the number of consecutive days ending today (going backwards) with a price less than or equal to today's. Constraints: 1 <= price <= 10^5; at most 10^4 calls.

💡 Core Algorithmic Approaches

  1. Maintain a monotonically decreasing stack of (price, span) pairs.
  2. When a new price arrives, pop every entry with a price at most the new one, accumulating their spans.
  3. The accumulated total plus one is the new span.
  4. Each entry is pushed and popped once, so the amortised cost is O(1).

💻 Benchmark Python3 Implementation

class StockSpanner:
    def __init__(self):
        self.st = []                       # (price, span), decreasing by price

    def next(self, price: int) -> int:
        span = 1
        while self.st and self.st[-1][0] <= price:
            span += self.st.pop()[1]       # absorb the smaller entries' spans
        self.st.append((price, span))
        return span

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) amortised per call: each entry is pushed and popped at most once.
💾 Space Complexity
O(n) for the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Using < instead of <=: the span includes days with an equal price, so the comparison must be non-strict.
  • Storing only prices: the accumulated spans are what make the algorithm amortised O(1) rather than O(n) per query.
  • Scanning backwards through all previous prices: O(n) per call.
  • Resetting the span on each call: the span accumulates across absorbed entries.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Stack Problems