Basics 0/97

Stacks and queues · 2 of 2

Monotonic stack

Find the next warmer day, the nearest smaller value and the maximum of every window in one pass each, by popping the entries a new value makes useless.

3,900 words · 18 min read

Part 1 of 8 Monotonic stack

Days until a warmer day

A weather app that prints "warmer in 4 days" under each day of a forecast answers one question for every position of a list: how far to the right is the first larger value? Many problems ask for the nearest larger or smaller value on one side of every position, and a stack answers each of them in a single pass over the list. We start with the weather version.

Difficulty tier:Normal

You get a list temperatures of daily temperatures. For each day, return how many days you have to wait after it for a strictly warmer temperature. If no warmer day comes, return 0 for that day.

Constraints

  • 1≤1 \le len(temperatures) ≤105\le 10^5
  • 30≤30 \le temperatures[i] ≤100\le 100

Sample 1 · Input

temperatures = [73,74,75,71,69,72,76,73]

Output

[1,1,4,2,1,1,0,0]

Sample 2 · Input

temperatures = [30,40,50,60]

Output

[1,1,1,0]

Sample 3 · Input

temperatures = [30,60,90]

Output

[1,1,0]

Number the days from 0. In the first sample, day 2 has temperature 75. Days 3, 4 and 5 are colder, at 71, 69 and 72, and day 6, at 76, is the first warmer one, so day 2 waits 6−2=46 - 2 = 4 days. Nothing after day 6 or day 7 is warmer, so they get 0.

The first sample. Each arrow joins a day to its first strictly warmer day, and the wait is the distance it spans.

The direct method looks ahead from each day until it finds a warmer one. That is quick on the sample, but consider a list in which the temperature never rises, such as 100,000 days at 50 degrees. No lookahead finds a warmer day, so each one runs to the end of the list. The first day is compared with 99,999 later days, the second with 99,998, and so on:

99,999+99,998+⋯+1+0=100,000×99,9992=4,999,950,000 comparisons99{,}999 + 99{,}998 + \dots + 1 + 0 = \frac{100{,}000 \times 99{,}999}{2} = 4{,}999{,}950{,}000 \text{ comparisons}

At about 10810^8 simple operations a second, that is around 50 seconds. The lookahead is slow because it reads the same days many times. Even in the sample, the lookahead from day 2 reads days 3, 4, 5 and 6, and then the lookaheads from days 3 and 4 read days 4 and 5 again.