Online Stock Span

Explanation & Solution

Description

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.

The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

Implement the StockSpanner class:

StockSpanner() Initializes the object of the class.
next(price) Returns the span of the stock's price given that today's price is price.

Examples

Example 1:

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]

null

Explanation:

StockSpanner stockSpanner = new StockSpanner();

stockSpanner.next(100); // return 1

stockSpanner.next(80); // return 1

stockSpanner.next(60); // return 1

stockSpanner.next(70); // return 2

stockSpanner.next(60); // return 1

stockSpanner.next(75); // return 4

stockSpanner.next(85); // return 6

Constraints

1 <= price <= 10^5
At most 5000 calls will be made to next

Approach

Stacks pattern

1. Stack of Price-Span Pairs

Maintain a stack where each entry stores {price, span}
The span records how many consecutive days (including itself) had prices ≤ that day's price

2. Processing Each New Price

Start with span = 1 (the current day itself)
While the stack's top has a price ≤ current price:
Pop it and absorb its span (add to current span)
This collapses all dominated days into the current span
Push the current {price, span} onto the stack

3. Monotonic Stack Property

The stack maintains prices in decreasing order from bottom to top
Each entry's span accounts for all the consecutive days it "covers"

Key Insight

By absorbing spans from popped entries, each price is processed in amortized O(1) time
The stack always contains potential "barriers" — days with prices higher than anything that came after them
Total time for n calls: O(n)

Solution Code

Remove All Adjacent Duplicates in String II

Car Fleet