Solution: Daily Temperatures

Statement

Given an array of integers, temperatures, that represents daily temperatures, return an array, output, where each element, output[i], indicates the number of days you need to wait after the $i^{th}$ day to experience a warmer temperature if there is no future day with a higher temperature, set output[i] to 0.

Constraints:

• $1 \leq$ temperatures.length $\leq 10^3$

• $30 \leq$ temperatures[i] $\leq100$

Solution

A monotonic stackA monotonic stack is a stack where elements are always in sorted order, making it useful for problems involving comparisons of numeric elements with relevant order. , particularly a decreasing one, is useful for solving problems where numeric comparisons depend on order. The concept involves storing indices of days in a stack, ensuring that the corresponding temperatures are in decreasing order. As we iterate through the temperature list, we compare the current day’s temperature with the temperature of the day at the top of the stack. If the current day’s temperature is not warmer, we add the current day’s index to the stack, indicating that no warmer day has been found yet. However, if the current day’s temperature is warmer, we pop indices from the stack until we find a day colder than the current one. For each popped index, we calculate the difference between the current day’s index and the popped index to determine the number of days it took to reach a warmer temperature.

The steps of the algorithm are as follows:

1. Create an array, output, of the same length as temperatures and initialize all its elements to 0.

2. Initialize an empty stack to keep track of the indices of the temperatures.

3. Loop through each index i of the temperatures array:

   1. While the stack is not empty and the current temperature, temperatures[i], is greater than the temperature at the index stored at the top of the stack:

      1. Pop the top index from the stack.

      2. Calculate the difference between the current index i and the popped index. This difference represents the number of days until a warmer temperature for the day at the popped index.

      3. Store this difference in the output array at the position of the popped index.

   2. Push the current index i onto the stack to continue tracking temperatures for future comparisons.

4. After processing all the temperatures, the output array will contain the number of days until a warmer temperature for each day. Return this output array as the result.

Let’s look at the following illustration to get a better understanding of the solution: