每日温度 图解题解

每日温度这道题在问什么

给一个数组 temperatures 记录每天气温，要求对每一天算出：再过几天会出现第一个比今天更高的温度，如果之后再也没有更高温就填 0。剥掉温度的外衣，它就是经典的「下一个更大元素」问题的距离版——对每个位置找右边第一个严格更大的元素，只是答案要的不是那个值，而是两者隔了几个位置。

为什么逐天向右扫的暴力会慢

最直觉的做法是对每一天都向右线性扫描，撞到第一个更高温为止，最坏 O(n²)。慢在重复劳动：一段连续降温的日子里，每一天都要把后面同样的区间再扫一遍。

换个视角看，某一天的答案要等到「未来某天」才揭晓。与其让每一天主动向右找，不如反过来：让还没等到答案的日子排队挂起，每来一个新温度，就检查队伍里有谁的答案在此刻揭晓，统一结算。这样每天只被处理常数次，扫描的浪费就消失了。

为什么栈里的温度天然是递减的

用一个栈保存「尚未找到答案」的下标。新温度 t 到来时，只要栈顶那天的温度比 t 低，它的答案就是今天，弹出结算；重复直到栈顶不再比 t 低，再把今天的下标压入。

注意一个自动成立的性质：留在栈里的温度从底到顶一定递减——因为任何比后来者低的栈顶都会在那一刻被弹掉，能留下的只有更高的。这个单调性正是效率的来源：结算时只需盯着栈顶弹，一旦栈顶不低于当前温度就能立刻停手，因为更深处的温度只会更高，它们还得继续等。这也是「单调栈」这个名字的含义。

弹出时下标差 i - j 为什么就是正确答案

当第 i 天把栈里的第 j 天弹出时，i 恰好是 j 之后第一个更高温的日子：j 与 i 之间的每一天都曾经入栈，却没能把 j 弹出，说明它们的温度都不超过第 j 天——中间没有任何一天满足条件，所以等待天数就是 i - j，不多不少。这也解释了栈里为什么必须存下标而不是温度：答案是位置差，只有温度算不出天数。

复杂度怎么数，边界坑在哪

时间 O(n)：虽然循环里套着 while，但每个下标一生至多入栈一次、出栈一次，总操作次数是 2n 级别。空间 O(n)：最坏温度一路走低，所有下标都压在栈里。

两个易错点：一是弹栈条件必须是严格大于，温度相等不算「更高温」，相等的那天还得继续等；二是扫完后仍留在栈里的日子，到最后也没等来更高温，它们的答案就是初始化的 0，不需要再补处理。

Python

def dailyTemperatures(T):
    ans = [0] * len(T)
    stack = []            # 存下标，温度递减
    for i, t in enumerate(T):
        while stack and t > T[stack[-1]]:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

C++

vector<int> dailyTemperatures(vector<int>& T){
    int n = T.size();
    vector<int> ans(n, 0);
    stack<int> st;            // 存下标
    for(int i = 0; i < n; i++){
        while(!st.empty() && T[i] > T[st.top()]){
            int j = st.top(); st.pop();
            ans[j] = i - j;
        }
        st.push(i);
    }
    return ans;
}

Java

public int[] dailyTemperatures(int[] T) {
    int n = T.length;
    int[] ans = new int[n];
    Deque<Integer> st = new ArrayDeque<>();   // 存下标
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && T[i] > T[st.peek()]) {
            int j = st.pop();
            ans[j] = i - j;
        }
        st.push(i);
    }
    return ans;
}