Description
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
Solutions
Solution 1: Monotonic Stack
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.
PythonJavaC++GoTypeScriptRustJavaScript
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stk = []
n = len(temperatures)
ans = [0] * n
for i in range(n - 1, -1, -1):
while stk and temperatures[stk[-1]] <= temperatures[i]:
stk.pop()
if stk:
ans[i] = stk[-1] - i
stk.append(i)
return ans(code-box)
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;
}
}(code-box)
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
stack<int> stk;
vector<int> ans(n);
for (int i = n - 1; ~i; --i) {
while (!stk.empty() && temperatures[stk.top()] <= temperatures[i]) {
stk.pop();
}
if (!stk.empty()) {
ans[i] = stk.top() - i;
}
stk.push(i);
}
return ans;
}
};(code-box)
func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
ans := make([]int, n)
stk := []int{}
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 && temperatures[stk[len(stk)-1]] <= temperatures[i] {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
ans[i] = stk[len(stk)-1] - i
}
stk = append(stk, i)
}
return ans
}(code-box)
function dailyTemperatures(temperatures: number[]): number[] {
const n = temperatures.length;
const ans: number[] = Array(n).fill(0);
const stk: number[] = [];
for (let i = n - 1; ~i; --i) {
while (stk.length && temperatures[stk.at(-1)!] <= temperatures[i]) {
stk.pop();
}
if (stk.length) {
ans[i] = stk.at(-1)! - i;
}
stk.push(i);
}
return ans;
}(code-box)
impl Solution {
pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
let n = temperatures.len();
let mut stk: Vec<usize> = Vec::new();
let mut ans = vec![0; n];
for i in (0..n).rev() {
while let Some(&top) = stk.last() {
if temperatures[top] <= temperatures[i] {
stk.pop();
} else {
break;
}
}
if let Some(&top) = stk.last() {
ans[i] = (top - i) as i32;
}
stk.push(i);
}
ans
}
}(code-box)
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function (temperatures) {
const n = temperatures.length;
const ans = Array(n).fill(0);
const stk = [];
for (let i = n - 1; ~i; --i) {
while (stk.length && temperatures[stk.at(-1)] <= temperatures[i]) {
stk.pop();
}
if (stk.length) {
ans[i] = stk.at(-1) - i;
}
stk.push(i);
}
return ans;
};(code-box)
