mediumStack / QueuePure DSA~25 min
Daily Price Span Streaming
A trading widget streams daily prices. For each day it must report the price span — the number of consecutive days up to and including today where the price was less than or equal to today's price.
Problem
Given an array prices of daily quotes processed left to right, return an array spans where spans[i] is the maximum number of consecutive days ending at day i (including day i) for which prices[j] <= prices[i].
Input
An integer array prices.
Output
An integer array spans of the same length.
Constraints
- 1 <= prices.length <= 100000
- 1 <= prices[i] <= 10^9
Examples
Example 1
Input
prices = [100,80,60,70,60,75,85]
Output
[1,1,1,2,1,4,6]
Each value counts the run of days at or below it ending today.
Example 2
Input
prices = [10,20,30]
Output
[1,2,3]
Each new day extends the rising span.