739. 每日温度
题目描述
输入整数数组 temperatures，temperatures[i] 是第 i 天的气温。
返回与它等长的数组 answer。answer[i] 等于从第 i 天往后，第一次出现严格更高气温的那一天与第 i 天相差的天数。
如果第 i 天之后再也没有更高的气温，answer[i] 为 0。
示例 1
输入：temperatures = [73,74,75,71,69,72,76,73] 输出：[1,1,4,2,1,1,0,0]
解释：例如第 2 天气温 75，下一次更高的是第 6 天的 76，相隔 4 天。
示例 2
输入：temperatures = [30,40,50,60] 输出：[1,1,1,0]
示例 3
输入：temperatures = [30,60,90] 输出：[1,1,0]
数据范围
1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100
解题思路：单调栈
单调递减栈结算更高温度。
为什么正确
栈内下标递增，对应温度单调不增（相等温度也保留）；每个下标等待右侧第一个严格更高温度。
复杂度分析
时间 O(n)，额外空间 O(n)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def dailyTemperatures(self,a):
out=[0]*len(a);st=[]
for i,x in enumerate(a):
while st and a[st[-1]]<x:j=st.pop();out[j]=i-j
st.append(i)
return outclass Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] out = new int[temperatures.length];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < temperatures.length; i++) {
while (!st.isEmpty() && temperatures[st.peek()] < temperatures[i]) {
int j = st.pop();
out[j] = i - j;
}
st.push(i);
}
return out;
}
}class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> out(temperatures.size(), 0);
vector<int> st;
for (int i = 0; i < (int)temperatures.size(); i++) {
while (!st.empty() && temperatures[st.back()] < temperatures[i]) {
int j = st.back();
st.pop_back();
out[j] = i - j;
}
st.push_back(i);
}
return out;
}
};func dailyTemperatures(temperatures []int) []int {
out := make([]int, len(temperatures))
st := []int{}
for i, x := range temperatures {
for len(st) > 0 && temperatures[st[len(st)-1]] < x {
j := st[len(st)-1]
st = st[:len(st)-1]
out[j] = i - j
}
st = append(st, i)
}
return out
}var dailyTemperatures = function(temperatures) {
const out = new Array(temperatures.length).fill(0), st = [];
for (let i = 0; i < temperatures.length; i++) {
while (st.length && temperatures[st[st.length - 1]] < temperatures[i]) {
const j = st.pop();
out[j] = i - j;
}
st.push(i);
}
return out;
};function dailyTemperatures(temperatures: number[]): number[] {
const out: number[] = new Array(temperatures.length).fill(0), st: number[] = [];
for (let i = 0; i < temperatures.length; i++) {
while (st.length && temperatures[st[st.length - 1]] < temperatures[i]) {
const j = st.pop()!;
out[j] = i - j;
}
st.push(i);
}
return out;
};其他解法
单调栈是“下一个更大元素”的通用模板；按温度记录依赖值域很小；从右向左跳跃省掉了栈，是单调栈思想的另一种实现。
解法 2：按温度记录最近位置 时间 O(n·m)，空间 O(m)
温度只有 30 到 100 共 m = 71 种。从右往左遍历，用数组 next[t] 记录温度 t 在当前位置右边最早出现的下标。对下标 i，枚举所有比 temperatures[i] 高的温度，取 next 中最小的下标得到答案，然后更新 next[temperatures[i]] = i。
利用了温度取值范围小的条件，思路直白。值域大时不可用，比单调栈慢约 m 倍。
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
INF = n + 1
nxt = [INF] * 101
ans = [0] * n
for i in range(n - 1, -1, -1):
t = temperatures[i]
best = INF
for w in range(t + 1, 101):
best = min(best, nxt[w])
if best < INF:
ans[i] = best - i
nxt[t] = i
return ansclass Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length, INF = n + 1;
int[] nxt = new int[101], ans = new int[n];
Arrays.fill(nxt, INF);
for (int i = n - 1; i >= 0; i--) {
int t = temperatures[i], best = INF;
for (int w = t + 1; w <= 100; w++) best = Math.min(best, nxt[w]);
if (best < INF) ans[i] = best - i;
nxt[t] = i;
}
return ans;
}
}class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size(), INF = n + 1;
vector<int> nxt(101, INF), ans(n, 0);
for (int i = n - 1; i >= 0; i--) {
int t = temperatures[i], best = INF;
for (int w = t + 1; w <= 100; w++) best = min(best, nxt[w]);
if (best < INF) ans[i] = best - i;
nxt[t] = i;
}
return ans;
}
};func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
INF := n + 1
nxt := make([]int, 101)
for w := range nxt {
nxt[w] = INF
}
ans := make([]int, n)
for i := n - 1; i >= 0; i-- {
t, best := temperatures[i], INF
for w := t + 1; w <= 100; w++ {
if nxt[w] < best {
best = nxt[w]
}
}
if best < INF {
ans[i] = best - i
}
nxt[t] = i
}
return ans
}var dailyTemperatures = function(temperatures) {
const n = temperatures.length, INF = n + 1;
const nxt = new Array(101).fill(INF), ans = new Array(n).fill(0);
for (let i = n - 1; i >= 0; i--) {
const t = temperatures[i];
let best = INF;
for (let w = t + 1; w <= 100; w++) best = Math.min(best, nxt[w]);
if (best < INF) ans[i] = best - i;
nxt[t] = i;
}
return ans;
};function dailyTemperatures(temperatures: number[]): number[] {
const n = temperatures.length, INF = n + 1;
const nxt: number[] = new Array(101).fill(INF), ans: number[] = new Array(n).fill(0);
for (let i = n - 1; i >= 0; i--) {
const t = temperatures[i];
let best = INF;
for (let w = t + 1; w <= 100; w++) best = Math.min(best, nxt[w]);
if (best < INF) ans[i] = best - i;
nxt[t] = i;
}
return ans;
}解法 3：从右向左跳跃 时间 O(n)，空间 O(1)
从右往左计算答案。对下标 i，从 j = i + 1 开始：如果 temperatures[j] 更高就找到了；否则比 j 温度低或相等的位置都不可能是答案，直接跳到 j + ans[j]。ans[j] 为 0 说明右边没有更高的，答案为 0。
复用已算出的答案做跳跃，除输出外只用 O(1) 空间。跳跃链就是从右向左的单调栈，均摊分析同样是 O(n)，但不如单调栈直观。
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans = [0] * n
for i in range(n - 2, -1, -1):
j = i + 1
while temperatures[j] <= temperatures[i]:
if ans[j] == 0:
j = -1
break
j += ans[j]
if j != -1:
ans[i] = j - i
return ansclass Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] ans = new int[n];
for (int i = n - 2; i >= 0; i--) {
int j = i + 1;
while (temperatures[j] <= temperatures[i]) {
if (ans[j] == 0) {
j = -1;
break;
}
j += ans[j];
}
if (j != -1) ans[i] = j - i;
}
return ans;
}
}class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n, 0);
for (int i = n - 2; i >= 0; i--) {
int j = i + 1;
while (temperatures[j] <= temperatures[i]) {
if (ans[j] == 0) {
j = -1;
break;
}
j += ans[j];
}
if (j != -1) ans[i] = j - i;
}
return ans;
}
};func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
ans := make([]int, n)
for i := n - 2; i >= 0; i-- {
j := i + 1
for temperatures[j] <= temperatures[i] {
if ans[j] == 0 {
j = -1
break
}
j += ans[j]
}
if j != -1 {
ans[i] = j - i
}
}
return ans
}var dailyTemperatures = function(temperatures) {
const n = temperatures.length;
const ans = new Array(n).fill(0);
for (let i = n - 2; i >= 0; i--) {
let j = i + 1;
while (temperatures[j] <= temperatures[i]) {
if (ans[j] === 0) {
j = -1;
break;
}
j += ans[j];
}
if (j !== -1) ans[i] = j - i;
}
return ans;
};function dailyTemperatures(temperatures: number[]): number[] {
const n = temperatures.length;
const ans: number[] = new Array(n).fill(0);
for (let i = n - 2; i >= 0; i--) {
let j = i + 1;
while (temperatures[j] <= temperatures[i]) {
if (ans[j] === 0) {
j = -1;
break;
}
j += ans[j];
}
if (j !== -1) ans[i] = j - i;
}
return ans;
}