Daily Temperatures

Problem

You are given an integer array temperatures where temperatures[i] is the forecast for day i. For every day, determine how many days you must wait until a strictly warmer day arrives. If no warmer day ever comes, the answer for that day is 0. Return the answers as an array answer of the same length.

• The forecast covers between 1 and 200,000 days.
• Each temperature is an integer between 20 and 110 inclusive.

Examples

• temperatures = [64, 68, 66, 66, 71, 60, 59, 75] → [1, 3, 2, 1, 3, 2, 1, 0]. Day 1 (68) waits three days for day 4 (71); the two 66s each wait for day 4 as well, so the first of them waits 2 and the second waits 1; day 7 never sees a warmer day.
• temperatures = [55, 62, 70, 81] → [1, 1, 1, 0]. Strictly increasing: every day is answered by the next one.
• temperatures = [95, 80, 80, 45] → [0, 0, 0, 0]. Nothing warmer ever arrives, and the tie between the two 80s does not count as warmer.

Hints

1. For each day, you are looking for the next day with a larger value. Which days can never be the answer for any earlier day once a warmer day has been seen?
2. Keep the days whose answer is still unknown. What ordering do their temperatures have?
3. Maintain a stack of indices with decreasing temperatures; when a warmer day arrives, pop every colder day and fill in its answer using the index difference.