Daily Temperatures

MediumArray Stack

A gardening app records each day's high temperature in temperatures, where temperatures[i] belongs to day i. Gardeners waiting to plant heat-loving seedlings see a countdown for every day: how many days they would have to wait, starting from that day, until a day that is strictly warmer.

Return an array answer of the same length, where answer[i] is that number of days. If no later day is warmer than day i, answer[i] is 0.

Example 1

Input: temperatures = [55,52,58,49,51,60]
Output: [2,1,3,1,1,0]

Explanation: From day 2 (58), the next warmer day is day 5 (60), three days later. Nothing comes after day 5, so it gets 0.

Example 2

Input: temperatures = [80,80,79]
Output: [0,0,0]

Explanation: A day with the same temperature is not warmer, and the temperature never rises.

Example 3

Input: temperatures = [65,64,70,63]
Output: [2,1,0,0]

Explanation: Nothing after day 2 beats 70, and day 3 is the last day.

Constraints

temperatures covers between 1 and 10^5 days.
Every temperature is an integer from 30 to 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