Daily Temperatures

Medium

Problem

For each day, return how many days you must wait until a warmer temperature, or 0 if no warmer day follows.

Example 1

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

Test cases

Case 1

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

Case 2

Input:    [30,40,50,60]
Expected: [1,1,1,0]

Case 3

Input:    [50]
Expected: [0]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Monotonic decreasing stack of indices

Time O(n)Space O(n)

Keep days still waiting for a warmer one. A warmer day pops and answers every colder day on top.

function dailyTemperatures(t) {
const res = new Array(t.length).fill(0), st = [];
for (let i = 0; i < t.length; i++) {
while (st.length && t[i] > t[st[st.length - 1]]) {
const j = st.pop();
res[j] = i - j;
}
st.push(i);
}
return res;
}