739. 每日温度

难度：🟡 Medium | 标签：单调栈 | 状态：⬜ LeetCode 链接

思路

单调递减栈（存下标）。 遇到比栈顶大的温度，循环弹出并计算 i - 栈顶下标。

代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& t) {
        int n = t.size();
        vector<int> res(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();
                res[j] = i - j;
            }
            st.push(i);
        }
        return res;
    }
};

复杂度

• 时间 O(n)（每个下标至多入出栈一次）
• 空间 O(n)

易错 / 回顾

• 存下标不是值
• 栈底是最大，「下一个更大」要求栈递减
• 一类「下一个更大 / 更小元素」全部走这个模板