Algorithm Day73 - Daily Temperatures

Posted on In , Views:

🧩 Problem Description

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 i-th day to get a warmer temperature.
If there is no future day for which this is possible, keep answer[i] == 0 instead.

💬 Examples

Example 1

1
2
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2

1
2
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3

1
2
Input: temperatures = [30,60,90]
Output: [1,1,0]

💡 Intuition

We can use a monotonic decreasing stack to keep track of temperatures indices:

  • Iterate through the array.
  • For each day, check if current temperature is higher than the one on top of the stack.
  • If yes, pop the index and calculate the difference in days.
  • Push the current index onto the stack.

🔢 Java Code (Monotonic Stack)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                answer[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        
        return answer;
    }
}

⏱ Complexity Analysis

  • Time: O(n) — each element pushed and popped at most once.
  • Space: O(n) — stack storage.

✍️ Summary

  • Use monotonic decreasing stack to track indices of temperatures.
  • For each warmer day, update result for all previous colder days.

Related problems

  • lc-496 — Next Greater Element I
  • lc-503 — Next Greater Element II
  • lc-42 — Trapping Rain Water