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
- Maintain a monotonically decreasing stack of
(price, span)pairs. - When a new price arrives, pop every entry with a price at most the new one, accumulating their spans.
- The accumulated total plus one is the new span.
- 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.