Daily Temperatures Medium 0 attempts
LeetCode ↗

Daily Temperatures

Medium Stack&Queue LeetCode

You're given a list of daily temperatures. For each day, work out how many days you'd need to wait before a warmer day arrives, placing that count at the matching index of the result; if no later day is ever warmer, use 0 instead.

Input Format
Implement dailyTemperatures(temperatures). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

Input
temperatures = [100,90,80]
Output
[0,0,0]
Constraints
  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100
Test Cases (2)
Case 1
Args: [[73,74,75,71,69,72,76,73]] Expected: [1,1,4,2,1,1,0,0]
Case 2
Args: [[100,90,80]] Expected: [0,0,0]
Topics
Stack&Queue

Monotonic Stack

Maintain a decreasing stack of indices.

javascript
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.

JavaScript