每日温度

GitHub跳转原题关系图返回列表

单调栈保存尚未遇到更高温度的下标，弹出时计算距离即为等待天数。

OJ: leetcodecn

题目 ID: daily-temperatures

难度:普及+/提高-

标签:单调栈栈

创建: 2026-07-29 12:10

更新: 2026-07-29 15:20

后置题目
roj 20025好的序列B 用单调栈维护后缀最小值阶梯拐点并弹出结算，沿用 A 的单调栈弹出结算候选这一骨架，但核心难度在容斥与奇偶 DPshumeng CSP202412E梦魔B 求两侧最近不小于自己的边界 L、R 就是 A 的单调栈弹出结算设备的两侧版本，再叠加端点贪心、嵌套区间限制与计数排序leetcodecn largest-rectangle-in-histogram柱状图中最大的矩形B 的柱状图最大矩形复用 A 教的「单调栈存下标、弹出时用下标差结算未解决候选」这一步（弹出后新栈顶即左界、当前 i 即右界），再叠加两侧第一个更矮的宽度语义与末尾补 0 哨兵。luogu P4393[BalticOI 2007] Sequence 序列问题B 的贡献法结算直接复用 A 教的「单调递减栈、遇更大值弹栈结算」这一步，且正是 A 弹栈语义（新栈顶=左侧第一个不小于它的值）给出 min(L,R) 的另一侧，再叠加全局最大值外每元素消失一次的贪心论证。luogu P2897[USACO08JAN] Artificial Lake GB 建最大笛卡尔树复用 A 的单调栈「保存未解决候选、遇到更高元素逐个弹出」这一步（弹出的低平台挂到新节点下），再叠加 A 未教的笛卡尔树建模与灌水淹没时刻递推。luogu P9485「LAOI-1」积水B 的第 3 步原样复用 A 教的「单调栈求每个元素左右第一个更高/不低于的位置」这一步来确定每个挡板的影响区间，再叠加 A 未教的前后缀最高值预处理与改低一个挡板的积水增量计算。

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定每日温度数组，对每一天找出下一个更高温度出现在几天后。

思路

从左到右扫描，维护单调栈（从栈底到栈顶温度递减）。栈中保存尚未遇到更高温度的下标：

  • 当前温度 temps[i] 比栈顶温度高时，栈顶位置找到了答案：answer[st.top()] = i - st.top()，弹出栈顶。
  • 重复直到栈顶温度不低于当前，然后压入当前下标。

扫描结束后栈中剩余的下标没有更高温度，答案保持 0。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> dailyTemperatures(vector<int> &temps) {
        int n = temps.size();
        vector<int> ans(n, 0);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && temps[st.top()] < temps[i]) {
                ans[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    for (int x : Solution().dailyTemperatures(a))
        cout << x << ' ';
    return 0;
}
python
#!/usr/bin/env python3
from typing import List


class Solution:
    def dailyTemperatures(self, temps: List[int]) -> List[int]:
        n = len(temps)
        ans = [0] * n
        st = []
        for i in range(n):
            while st and temps[st[-1]] < temps[i]:
                ans[st.pop()] = i - st[-1]
            st.append(i)
        return ans


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(*Solution().dailyTemperatures(a))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n)O(n)，每个下标最多入栈、出栈一次。
  • 空间复杂度：O(n)O(n)，栈最多存所有下标。

总结

单调栈的核心是"栈中保存尚未解决的候选"，遇到更大的值时逐个结算。本题栈存下标而非值，弹出时用下标差计算距离。