26. Daily Temperatures

You are given an array temperatures where temperatures[i] is the temperature recorded on day i.

Return an array answer of the same length where answer[i] is the number of days you would have to wait after day i to see a strictly warmer temperature. If no later day is warmer, answer[i] is 0.

Example 1

Input: temperatures = [70,72,68,65,69,75]
Output: [1,4,2,1,1,0]

Explanation: After day 1 (72) the next warmer day is day 5 (75), four days later. Day 5 is the last day, so it gets 0.

Example 2

Input: temperatures = [50,50,50]
Output: [0,0,0]

Explanation: An equal temperature does not count as warmer.

Example 3

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

Constraints

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

💡 Hint 1

Checking every later day for each day is O(n²). Can one pass settle several days at once?

💡 Hint 2

Keep the indices of days that are still waiting for a warmer day. Their temperatures are non-increasing from bottom to top.

💡 Hint 3

When today is warmer than the day on top of that stack, today is the answer for that day: pop it and record the distance.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Use a monotonic stack of indices whose warmer day has not been found yet; their temperatures never increase from the bottom of the stack to the top. For each day i, while the stack is non-empty and temperatures[i] is strictly greater than the temperature at the top index j, pop j and set answer[j] = i - j. Then push i. Indices left on the stack at the end never see a warmer day and keep the default 0. Each index is pushed and popped at most once, so the whole scan is linear.

Time O(n)Space O(n)

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const answer = new Array(n).fill(0);
  const stack = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const j = stack.pop();
      answer[j] = i - j;
    }
    stack.push(i);
  }
  return answer;
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        int[] stack = new int[n];
        int top = -1;
        for (int i = 0; i < n; i++) {
            while (top >= 0 && temperatures[i] > temperatures[stack[top]]) {
                int j = stack[top--];
                answer[j] = i - j;
            }
            stack[++top] = i;
        }
        return answer;
    }
}

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
function dailyTemperatures(temperatures) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit