小旭讲解 LeetCode 739. Daily Temperatures
小旭讲解 LeetCode 739. Daily Temperatures

题目

LeetCode 739. 每日温度

思路

该题是一个典型的单调队列模型的问题 —— 最近第一个更大的数,该类型的问题在基础算法系列里面有讲解,大家可以看下 [应用] 左侧第一个小的值 ,在此不再赘述。

在理解了上面的题目后,需要灵活应对如下问题:

  • 如何求出每个数左边的第一个相对自己更大的值
  • 如何求出每个数左边的第一个相对自己更小的值
  • 如何求出每个数右边的第一个相对自己更大的值
  • 如何求出每个数右边的第一个相对自己更小的值

代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> st; // idx for element in T
        int n=T.size();
        vector<int> ans(n,0);
        for (int i=n-1;i>=0;--i) {
            while(!st.empty() && T[st.top()] <= T[i]) st.pop();
            if (st.empty()) ans[i]=0;
            else ans[i]=st.top()-i;
            st.push(i);
        }
        return ans;
    }
};
欢迎分享,引用。若转载,请联系我,谢谢配合。
本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-739-daily-temperatures/
0 0 vote
Article Rating
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments