Practice › Stack & Queue
Daily Temperatures
Medium · Stack & Queue · Asked at Amazon, Google, Meta, Microsoft
For each day, print how many days you have to wait for a warmer temperature. If no warmer day comes, print 0 for that day.
Input
First line: n. Second line: n space-separated integers.
Output
n space-separated waits.
Constraints
- 1 ≤ n ≤ 10^5
- 30 ≤ t[i] ≤ 100
A stack of indices whose answer is still unknown, with decreasing temperatures. A warmer day pops (and answers) all colder days on top.
Example 1
Input
8 73 74 75 71 69 72 76 73
Output
1 1 4 2 1 1 0 0
Example 2
Input
4 30 40 50 60
Output
1 1 1 0
Hints
- Keep a stack of indices of days still waiting for a warmer day.
- When a warmer day i arrives, pop every colder day j from the stack and set answer[j] = i − j.
Approach
The stack holds indices with non-increasing temperatures. For day i, while the top day is colder than t[i], it has found its answer: ans[top] = i − top; pop it. Then push i. Days left on the stack at the end never get warmer, so their answer stays 0.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> t(n), ans(n, 0), st;
for (auto &x : t) cin >> x;
for (int i = 0; i < n; i++) {
while (!st.empty() && t[st.back()] < t[i]) {
ans[st.back()] = i - st.back();
st.pop_back();
}
st.push_back(i);
}
for (int i = 0; i < n; i++) cout << ans[i] << (i + 1 < n ? " " : "\n");
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
t = data[1:]
ans, st = [0] * len(t), []
for i, x in enumerate(t):
while st and t[st[-1]] < x:
j = st.pop()
ans[j] = i - j
st.append(i)
print(*ans)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] t = new int[n], ans = new int[n], st = new int[n];
for (int i = 0; i < n; i++) t[i] = sc.nextInt();
int top = 0;
for (int i = 0; i < n; i++) {
while (top > 0 && t[st[top - 1]] < t[i]) {
int j = st[--top];
ans[j] = i - j;
}
st[top++] = i;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(ans[i]).append(i + 1 < n ? " " : "");
System.out.println(sb);
}
}