All problems

Heatwave Span

Medium · stack

A weather station records one temperature per day. You are given a list temps where temps[i] is the temperature on day i.

For each day, find how many consecutive days ending on that day (counting the day itself) had a temperature no higher than that day's temperature. Go back one day at a time and stop as soon as you meet a day that is strictly hotter, or you run out of days.

Return a list span of the same length as temps, where span[i] is that count. Equal temperatures do not stop the count. Every span[i] is at least 1, because a day always counts itself.

Examples

Example 1

Input: temps = [3, 1, 2, 4, 4, 2]

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

Day 3 (4) looks back past 2, 1 and 3, all no higher, so the span is 4. Day 4 (4) also reaches back to the start, so 5. Day 5 (2) is stopped at once by the hotter 4 before it.

Example 2

Input: temps = [5, 4, 3]

Output: [1, 1, 1]

Every day is preceded by a hotter one, so each span is just the day itself.

Example 3

Input: temps = [-1, 0, -5, 7]

Output: [1, 2, 1, 4]

Constraints