---
comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/solution/0700-0799/0739.Daily%20Temperatures/README.md
tags:
- 栈
- 数组
- 单调栈
---
# [739. 每日温度](https://leetcode.cn/problems/daily-temperatures)
[English Version](/solution/0700-0799/0739.Daily%20Temperatures/README_EN.md)
## 题目描述
给定一个整数数组 temperatures
,表示每天的温度,返回一个数组 answer
,其中 answer[i]
是指对于第 i
天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0
来代替。
示例 1:
输入: temperatures
= [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
提示:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
## 解法
### 方法一:单调栈
单调栈常见模型:找出每个数左/右边**离它最近的**且**比它大/小的数**。模板:
```python
stk = []
for i in range(n):
while stk and check(stk[-1], i):
stk.pop()
stk.append(i)
```
对于本题,我们需要找出每个数右边**离它最近的**且**比它大的数**,因此我们可以从右往左遍历数组,且需要维护一个从栈底到栈顶单调递减的栈。
对于当前遍历到的数 `temperatures[i]`,如果栈顶元素 `temperatures[stk[-1]]` 小于等于 `temperatures[i]`,则弹出栈顶元素,直到栈为空或者栈顶元素大于 `temperatures[i]`。如果此时栈不为空,那么栈顶元素就是 `temperatures[i]` 右边离它最近的且比它大的数,更新 `ans[i] = stk[-1] - i`。接着,我们将 $i$ 入栈,继续遍历下一个数。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为 `temperatures` 数组的长度。
#### Python3
```python
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
ans = [0] * len(temperatures)
stk = []
for i, t in enumerate(temperatures):
while stk and temperatures[stk[-1]] < t:
j = stk.pop()
ans[j] = i - j
stk.append(i)
return ans
```
#### Java
```java
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] ans = new int[n];
Deque stk = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
while (!stk.isEmpty() && temperatures[stk.peek()] < temperatures[i]) {
int j = stk.pop();
ans[j] = i - j;
}
stk.push(i);
}
return ans;
}
}
```
#### C++
```cpp
class Solution {
public:
vector dailyTemperatures(vector& temperatures) {
int n = temperatures.size();
vector ans(n);
stack stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
ans[stk.top()] = i - stk.top();
stk.pop();
}
stk.push(i);
}
return ans;
}
};
```
#### Go
```go
func dailyTemperatures(temperatures []int) []int {
ans := make([]int, len(temperatures))
var stk []int
for i, t := range temperatures {
for len(stk) > 0 && temperatures[stk[len(stk)-1]] < t {
j := stk[len(stk)-1]
ans[j] = i - j
stk = stk[:len(stk)-1]
}
stk = append(stk, i)
}
return ans
}
```
#### TypeScript
```ts
function dailyTemperatures(temperatures: number[]): number[] {
const n = temperatures.length;
const ans = new Array(n).fill(0);
const stk: number[] = [];
for (let i = n - 1; i >= 0; --i) {
while (stk.length && temperatures[stk[stk.length - 1]] <= temperatures[i]) {
stk.pop();
}
if (stk.length) {
ans[i] = stk[stk.length - 1] - i;
}
stk.push(i);
}
return ans;
}
```
#### Rust
```rust
impl Solution {
pub fn daily_temperatures(temperatures: Vec) -> Vec {
let n = temperatures.len();
let mut stack = vec![];
let mut res = vec![0; n];
for i in 0..n {
while !stack.is_empty() && temperatures[*stack.last().unwrap()] < temperatures[i] {
let j = stack.pop().unwrap();
res[j] = (i - j) as i32;
}
stack.push(i);
}
res
}
}
```
#### JavaScript
```js
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function (temperatures) {
const n = temperatures.length;
const ans = new Array(n).fill(0);
const stk = [];
for (let i = n - 1; i >= 0; --i) {
while (stk.length && temperatures[stk[stk.length - 1]] <= temperatures[i]) {
stk.pop();
}
if (stk.length) {
ans[i] = stk[stk.length - 1] - i;
}
stk.push(i);
}
return ans;
};
```
### 方法二
#### Python3
```python
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
stk = []
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
```
#### Java
```java
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
Deque 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;
}
}
```
#### C++
```cpp
class Solution {
public:
vector dailyTemperatures(vector& temperatures) {
int n = temperatures.size();
vector ans(n);
stack stk;
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;
}
};
```
#### Go
```go
func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
ans := make([]int, n)
var 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
}
```