LeetCode 739. 每日温度

◎

本节目标

用单调栈保存尚未遇到更高温度的日期下标，并在答案确定时弹栈。

查看 LeetCode 原题

题意与边界

对每一天，求之后第一次出现更高温度还需等待几天；不存在时答案为 0。相同温度不算升高，因此不能提前结算。

尚未解决的下标栈

栈 pending 保存还没找到下一次更高温度的日期下标，其对应温度从栈底到栈顶单调不增。扫描到新温度时，只要它严格高于栈顶日期，就弹出该下标，并用两者下标差填写答案；随后当前下标入栈等待未来温度。

正确性依据

某下标留在栈中，说明从它之后到当前之前都没有更高温度。它第一次因当前温度而弹出时，当前下标自然是最近的严格更高日期。未弹出的下标直到扫描结束都没有更高温度，初始化的 0 正是所需答案。

代码实现

C++

C++17

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> answer(temperatures.size(), 0);
        vector<int> pending;
        for (int i = 0; i < static_cast<int>(temperatures.size()); i++) {
            while (!pending.empty() && temperatures[pending.back()] < temperatures[i]) {
                int prev = pending.back();
                pending.pop_back();
                answer[prev] = i - prev;
            }
            pending.push_back(i);
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        answer = [0] * len(temperatures)
        pending = []
        for i, temperature in enumerate(temperatures):
            while pending and temperatures[pending[-1]] < temperature:
                prev = pending.pop()
                answer[prev] = i - prev
            pending.append(i)
        return answer

复杂度分析

• 时间复杂度：O(n)，每个下标至多入栈、出栈各一次。
• 空间复杂度：O(n)，最坏情况下所有下标都留在栈中。

易错点

• 使用小于等于比较，让相同温度错误地结算答案。
• 栈中保存温度而不是下标，无法计算等待天数。
• 反复向后查找，退化为 O(n²)。

模式迁移

当问题询问“右侧第一个更大或更小元素”时，单调栈保存尚未解决的位置，并在新元素成为答案时批量结算。