Daily Temperatures
For each day, count how many days must pass until a strictly warmer temperature. Use zero when no warmer future day exists.
Work through the cases
3 examplesInput notation
Daily temperatures separated by spaces.Expected result
The waiting times separated by spaces.Case 1
Input
30 40 35 50
Expected output
1 2 1 0
Case 2
Input
50 40
Expected output
0 0
Case 3
Input
30 30 30
Expected output
0 0 0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
For each day, the wait until a warmer day. n ≤ 10^5 forbids a rightward scan from every index. This is next-greater-element. A monotonic stack of indices still waiting for a warmer day, scanned right to left, pops every temperature that is not strictly warmer; the new top is the answer. Temperatures increase from top to bottom. Each index is pushed and popped once, O(n).
This problem requires us to find the position of the first element greater than each element to its right, which is a typical application scenario for a monotonic stack.
We traverse the array temperatures from right to left, maintaining a stack stk that is monotonically increasing from top to bottom in terms of temperature. The stack stores the indices of the array elements. For each element temperatures[i], we continuously compare it with the top element of the stack. If the temperature corresponding to the top element of the stack is less than or equal to temperatures[i], we pop the top element of the stack in a loop until the stack is empty or the temperature corresponding to the top element of the stack is greater than temperatures[i]. At this point, the top element of the stack is the first element greater than temperatures[i] to its right, and the distance is stk.top() - i. We update the answer array accordingly. Then we push temperatures[i] onto the stack and continue traversing.
After the traversal, we return the answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array temperatures.
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
Deque<Integer> stk = new ArrayDeque<>();
int[] ans = new int[n];
for (int i = n - 1; i >= 0; --i) {
while (!stk.isEmpty() && temperatures[stk.peek()] <= temperatures[i]) {
stk.pop();
}
if (!stk.isEmpty()) {
ans[i] = stk.peek() - i;
}
stk.push(i);
}
return ans;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.