Daily Temperatures

Problem Statement

In this problem statement, you are provided with an array temperatures where each element in the array represents the temperature of a day. The task is to determine the number of days one has to wait for a temperature that's warmer than the current day's temperature. The result should be an array answer where answer[i] indicates the number of days to wait after day i to experience a warmer day. If no such future day is warmer, then answer[i] should be set to 0. The challenge is to efficiently navigate through the temperatures array and compute the required days for each temperature.

Examples

Example 1

Input:

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

Output:

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

Example 2

Input:

temperatures = [30,40,50,60]

Output:

[1,1,1,0]

Example 3

Input:

temperatures = [30,60,90]

Output:

[1,1,0]

Constraints

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

Approach and Intuition

To solve this problem efficiently while keeping the time complexity in check, we can employ a stack data structure to help trace days with warmer temperatures dynamically as we iterate through the list:

1. Initialize an empty stack and an array answer of the same length as temperatures, filled initially with zeros.
2. Iterate through the temperatures list using an index i:
   • While the stack is not empty and the current temperature temperatures[i] is greater than the temperature at the index represented by the top of the stack (temperatures[stack[-1]]):
     • Pop the index from the stack and calculate the difference between the current index i and the popped index. This represents how many days the warmer temperature was awaited.
     • Update answer at the popped index with this difference.
   • Push the current index i onto the stack.
3. The stack helps in remembering indices of temperatures for which we haven't yet found a warmer day. The usage of the stack ensures that each index is pushed and popped only once, leading to a time complexity of O(n).

Examples Explained:

• For temperatures = [73, 74, 75, 71, 69, 72, 76, 73], the process is as follows:
  • Start with day 0 (73°F). It's warmer the very next day (74°F), hence answer[0] = 1.
  • For day 2 (75°F), it takes 4 more days until it reaches 76°F, so answer[2] = 4.
  • Days that are at the end of the array or do not have any warmer days following them will record a 0, such as answer[6] and answer[7] since 76°F and 73°F are the last temperatures without any warmer days ahead.

This approach ensures that for each day we are capturing the wait-time efficiently for a warmer day or establishing that no warmer day exists.

Solutions

class Solution {
    public int[] forecastHeating(int[] temps) {
        int len = temps.length;
        int maxTemp = 0;
        int result[] = new int[len];
            
        for (int i = len - 1; i >= 0; i--) {
            int tempToday = temps[i];
            if (tempToday >= maxTemp) {
                maxTemp = tempToday;
                continue;
            }
                
            int delay = 1;
            while (temps[i + delay] <= tempToday) {
                // Update delay based on previously computed results
                delay += result[i + delay];
            }
            result[i] = delay;
        }
            
        return result;
    }
}