All problems

Online Stock Span

Medium · stack

A share price is recorded once per day, and prices[i] is the price on day i.

The span of a day is the number of consecutive days, counting that day itself and going backwards, whose price was less than or equal to that day's price. The count stops at the first earlier day with a higher price, or at the first recorded day.

Return a list with the span of every day, in order.

Examples

Example 1

Input: prices = [100, 80, 60, 70, 60, 75, 85]

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

On the day priced 75, the days priced 75, 60, 70 and 60 all count, but 80 is higher, so the span is 4. On the day priced 85 everything back to the 80 counts, giving 6.

Example 2

Input: prices = [20, 20, 30, 10]

Output: [1, 2, 3, 1]

An equal price counts, so the second 20 has span 2. The day priced 10 is below the day before it, so it only counts itself.

Constraints