546. Online Stock Span
Prices of a stock arrive one per day, in order. The span of today's price is the number of consecutive days, ending today and counting today, on which the price was less than or equal to today's price.
Implement a class StockSpanner with one operation:
next(price)— record today'spriceand return its span.
For instance, if the prices so far are [7, 2, 1, 2] and today's price is 2, the span is 4: today plus the three previous days, since 2, 1, 2 are all <= 2 — the streak only breaks at 7.
Each next call must answer before seeing any future prices. Can you make the total work linear in the number of calls?
Example 1:
Input: next(100), next(80), next(60), next(70), next(60), next(75), next(85)
Output: 1, 1, 1, 2, 1, 4, 6
Explanation: For the price 75, the streak of days with price <= 75 running backwards from it is 75, 60, 70, 60 — four days (80 breaks it). For 85 the streak is 85, 75, 60, 70, 60, 80 — six days.
Example 2:
Input: next(31), next(41), next(48), next(59), next(26)
Output: 1, 2, 3, 4, 1
Explanation: Prices rise for four days, so each day's span covers everything so far; the drop to 26 resets the streak to a single day.
Constraints:
- 1 ≤ q ≤ 10⁴
- 1 ≤ price ≤ 10⁵
- Days on which the earlier price equals today's price count toward the span.
Hints:
The span stops at the nearest previous day with a price STRICTLY greater than today's. So the question is really: where is the previous greater element?
Keep a stack of days whose prices form a strictly decreasing sequence. A new price pops every day it dominates — those days can never end anyone's streak again.
Store each stack entry as (price, span). When you pop an entry, absorb its span into today's; each day is pushed once and popped at most once, so all q calls together cost O(q).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: next(100), next(80), next(60), next(70), next(60), next(75), next(85)
Expected output: 1, 1, 1, 2, 1, 4, 6