【栈 - LeetCode】739.每日温度

Lokinli

发布于 2025-08-26 08:08:26

11400

代码可运行

文章被收录于专栏：以终为始以终为始

运行总次数：0

代码可运行

739. 每日温度 - 力扣（LeetCode）

题解

暴力+技巧

官网给的一个暴力遍历的方式，技巧点在于，温度的最大值是 100，因此里面的 for 循环可以通过控制最大是到 100 来降低时间复杂度。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int>ans(n), next(101, INT_MAX);
        for(int i = n - 1; i >= 0; i --){
            int index = INT_MAX;
            for(int t = temperatures[i] + 1; t <= 100; t ++){
                index = min(index, next[t]);
            }
            if(index != INT_MAX){
                ans[i] = index - i;
            }
            next[temperatures[i]] = i;
        }
        return ans;
    }
};

单调栈

栈中存储还没有被找到的满足条件的第 x 天。

如果是递增序列，栈中始终就一个元素，不断移入移出。

如果是非递增，则一直入栈，找到第一个大于栈顶的，再依次出栈判断。

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-25，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历