LeetCode739. 每日温度（2024冬季每日一题 15）

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• $1<=temperatures.length<=10^5$
• $30<=temperatures[i]<=100$

---

思路：单调栈

• 反向遍历数组，通过单调栈找出当前元素右边，比当前元素大的，切最近的元素
• 记录其下标，这个下标 减 当前下标，就是结果（右边第几个比它大

class Solution {
public:
    stack<int> stk;
    vector<int> dailyTemperatures(vector<int>& t) {
        int n = t.size();
        vector<int> res;
        for(int i = n - 1; i >= 0; i--){
            while(!stk.empty() && t[stk.top()] <= t[i]) stk.pop();
            if(stk.empty()) res.push_back(0);
            else res.push_back(stk.top() - i);
            stk.push(i);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

原文地址：https://blog.csdn.net/qq_46456049/article/details/144025010

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！