Online Stock Span

Medium· monotonic stack· previous greater

Problem

Prices arrive one per day. For each new price, return its span: the number of consecutive days ending today (including today) on which the price was less than or equal to today's price.

Examples

Input: next(100), next(80), next(60), next(70), next(60), next(75), next(85)

Output: [1,1,1,2,1,4,6]

For 75, the run 60, 70, 60, 75 are all <= 75, giving a span of 4.

Constraints

• 1 <= price <= 10^5
• At most 10^4 calls to next

Hints & approach

Hint 1

This is a "previous greater element" question asked online.

Hint 2

Once a price is covered by a larger later price, it can never be the blocker again.

Hint 3

Store (price, span) pairs so popped days contribute their spans.

Approachtry the hints first

Keep a stack of (price, span) pairs with strictly decreasing prices. When a new price arrives, start span = 1 and pop every pair whose price is <= the new price, adding its span to ours. Push (price, span) and return span. Popped entries are absorbed into the new one, so each price is pushed and popped once in total, giving amortised O(1) per call.

Time O(1) amortised per call · Space O(n)

← PreviousDaily Temperatures Next →Remove K Digits