739. Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

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

Solution:

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];

        Deque<Integer> stack = new ArrayDeque<>();
        //   0 1  2   3 4  5   6  7
        // [73,74,75,71,69,72,76,73]
        //                     i
        // 7, 6
        for (int i = 0; i < n; i++){
            int currentTemp = temperatures[i];
            // 73 // 74  // 75  // 71  // 69 // 72// 76 // 73

            // ! && 73 < 74     // ! && 74 <75 
            // 0 ///  1
            // answer[0] = 1 - 0 = 1;  // a[1] = 2 - 1 = 1 
            // ! && 75 > 71 
            // ! && 71 > 69
            // ! && 69 < 72
            // 4   
            // answer[4] = 5 - 4 = 1 
            // ! && 71 < 72 
            // answer[3] = 5 -3 = 2
            // ! && 75 > 72 

            // ! && 72 < 76 
            // answer[5] = 6 - 5 = 1
            // ! && 75 < 76 
            // answer[2] = 6 -2 =4

            // ! && 76 > 73 
            //
            while(!stack.isEmpty() && temperatures[stack.peek()] < currentTemp){
                int prevDay = stack.pollFirst();
                answer[prevDay] = i - prevDay;
            }

            stack.offerFirst(i);
        }

        return answer;
    }
}
// TC: O(n)
// SC: O(n)