Design a data structure that processes stock prices one by one and returns the span for each new price.
You are given a stream of daily stock prices. For each new price, compute its span: the number of consecutive days ending on the current day for which the price was less than or equal to the current price.
Implement a data structure that supports repeatedly inserting the next stock price and returning its span immediately.
Input Format
The task is interactive in spirit:
next(price)is called multiple times, once per incoming stock price.- Each call receives one integer
price. - Return the span for that price.
Output Format
For each call to next(price), return one integer equal to the stock span of the given price.
Constraints
- Prices are positive integers.
- Calls are processed in order.
- Aim for an efficient per-call solution over the entire stream.
- The exact numeric limits are not essential here; a solution should comfortably handle long sequences.
Example 1
Input
[
Output
[
Explanation
Illustrative example:
Calls:
- next(100) -> 1
- next(80) -> 1
- next(60) -> 1
- next(70) -> 2
- next(60) -> 1
- next(75) -> 4
- next(85) -> 6
Spans count consecutive days ending today with price <= current price.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.