Daily Temperatures [Medium] — Monotonic Stack

Problem Statement

Given temperatures, return an array answer where answer[i] is the number of days until a warmer temperature after day i. 0 if no such day.

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

Intuition

Maintain a monotonic decreasing stack of indices. When we see a warmer temperature, pop all cooler indices from the stack and compute their wait.

Solutions

C++

vector<int> dailyTemperatures(vector<int>& T) {
    int n=T.size();
    vector<int> ans(n,0);
    stack<int> stk;
    for (int i=0;i<n;i++) {
        while (!stk.empty() && T[i]>T[stk.top()]) {
            ans[stk.top()] = i-stk.top(); stk.pop();
        }
        stk.push(i);
    }
    return ans;
}

Java

public int[] dailyTemperatures(int[] T) {
    int n=T.length;
    int[] ans=new int[n];
    Deque<Integer> stk=new ArrayDeque<>();
    for (int i=0;i<n;i++) {
        while (!stk.isEmpty()&&T[i]>T[stk.peek()]) ans[stk.peek()]=i-stk.pop();
        stk.push(i);
    }
    return ans;
}

JavaScript

var dailyTemperatures = function(T) {
    const ans=new Array(T.length).fill(0), stk=[];
    for (let i=0;i<T.length;i++) {
        while (stk.length&&T[i]>T[stk.at(-1)]) ans[stk.at(-1)]=i-stk.pop();
        stk.push(i);
    }
    return ans;
};

Python

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    ans = [0] * len(temperatures)
    stack = []  # indices, monotone decreasing by temperature
    for i, t in enumerate(temperatures):
        while stack and t > temperatures[stack[-1]]:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

Complexity

Time: O(n) — each element pushed/popped once
Space: O(n)