Daily Temperatures | Problems

Given an array of daily temperatures, return an array where answer[i] is the number of days you have to wait after day i to get a warmer temperature. If no future day is warmer, answer[i] = 0.

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

Sample Input

—

Sample Output

—

Constraints

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

Test Cases

Case 1

Args: [[73,74,75,71,69,72,76,73]] Expected: [1,1,4,2,1,1,0,0]

Topics

Stack&Queue

Monotonic Stack

Maintain a decreasing stack of indices.

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

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.