题目描述

给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如：temperatures = [73,74,75,71,69,72,76,73]，输出 [1,1,4,2,1,1,0,0]。

解释：第 0 天温度 73，下一天（第 1 天）温度 74 > 73，所以 answer[0] = 1；第 2 天温度 75，4 天后（第 6 天）温度 76 > 75，所以 answer[2] = 4。

解题思路

本题是经典的单调栈问题——更具体地说，是单调递减栈的应用，用来寻找每个元素右侧第一个比它大的元素的距离。

暴力解法

对于每一天，向后扫描直到找到更高的温度，时间复杂度为 O(n^2)。当 n = 10^5 时会超时。

单调栈解法

核心思想：维护一个从栈底到栈顶递减（指温度值）的栈，栈中存储的是下标而非温度值。

  1. 遍历温度数组，对于每一天 i：
  2. 当栈不为空，且当前温度 temperatures[i] 大于栈顶下标对应的温度 temperatures[stack.peek()] 时：
    • 说明栈顶这一天终于等到了更高的温度！
    • 弹出栈顶下标 index，计算 answer[index] = i - index。
    • 继续检查新的栈顶，直到不满足条件为止。
  3. 将当前下标 i 入栈。

为什么单调栈可以解决问题？

以 [73,74,75,71,69,72,76,73] 为例，在遍历到第 5 天（温度 72）之前：

  • 栈内存储的是 [75, 71, 69] 的下标（即 [2, 3, 4]），温度从底到顶是递减的。

当 i=5（温度 72）到来时：

  • 72 > 69 → 弹出 69（下标 4），answer[4] = 5-4 = 1
  • 72 > 71 → 弹出 71（下标 3），answer[3] = 5-3 = 2
  • 72 < 75 → 停止，将 72（下标 5）入栈

单调栈保证了每个元素最多进栈一次、出栈一次，从而将时间复杂度从暴力的 O(n²) 降为 O(n)。

核心要点

  • 存储下标而非值，是为了方便计算距离 i - index。
  • 当栈中仍有剩余元素时，说明这些天之后没有更高的温度，answer 数组的对应位置保持默认值 0 即可。

复杂度分析

  • 时间复杂度：O(n)，每个下标最多入栈一次、出栈一次，所有操作均摊下来是 O(1)。
  • 空间复杂度：O(n)，最坏情况下栈中可能存储所有下标（单调递减序列）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package code.J739;

import java.util.ArrayDeque;
import java.util.Deque;

public class J739 {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int index = stack.pop();
                res[index] = i - index;
            }
            stack.push(i);
        }
        return res;
    }
}