## What is it? Design a data structure that answers "stock span" queries online: for each day's price, return how many consecutive days (including today) the price has been ≤ today's price. ## How it works - Maintain a stack of `(price, span)` pairs - For each new price: - Initialize `span = 1` - While the stack top price ≤ current price → add the span of the top to current span, pop - Push `(current price, current span)` onto the stack - Return the current span ## When to use - Online stock span queries arriving one price at a time - Problems asking for the "range of dominance" or "how far back does the current value win" ## Key Points - O(1) amortized per query — each element is pushed and popped at most once across all queries - O(n) space overall - Monotonic decreasing price stack - Great example of aggregating information into the stack itself (storing span, not just index)