leetcode 739 每日温度

简介: leetcode 739 每日温度

每日温度


dec6aff83c3e4ffb96781add45cabe68.png

单调栈


通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了。


用temperatures = [73, 74, 75, 71, 71, 72, 76, 73]为例来逐步分析,输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。


首先先将第一个遍历元素加入单调栈


b4e2f0c7d883418785d6b8118969ef7e.png

加入T[1] = 74,因为T[1] > T[0],而我们要保持一个递增单调栈(从栈头到栈底),所以将T[0]弹出,T[1]加入,此时result数组可以记录了,result[0] = 1,即T[0]右面第一个比T[0]大的元素是T[1]。


68685fe767fd4dc2b7d3de5ebcc874a6.png

加入T[2],同理,T[1]弹出



8e534c1f35c34724bb13b4872834ed53.png

加入T[3],T[3] < T[2] (当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况),加T[3]加入单调栈。

35e49459dcf44870aac7e8d245f2ad20.png

加入T[4],T[4] == T[3] (当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况),此时依然要加入栈,不用计算距离,因为我们要求的是右面第一个大于本元素的位置,而不是大于等于!

0fc710f7e9d8445c90763b6d3ea5a40c.png


  • 加入T[5],T[5] > T[4] (当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况),将T[4]弹出,同时计算距离,更新result

8a9ddea8a8b94072a00c08f55c41374e.png

  • T[4]弹出之后, T[5] > T[3] (当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况),将T[3]继续弹出,同时计算距离,更新result

9e60073a713b429eb701b11821ecb6cd.png

直到发现T[5]小于T[st.top()],终止弹出,将T[5]加入单调栈


1f5341f255f343ae80550b9399f80e55.png

加入T[6],同理,需要将栈里的T[5],T[2]弹出


a8ef2bd940a84e729f5e13a3ec593883.png

同理,继续弹出

6cc2cd79f5394bf6b8b0473034421a14.png

此时栈里只剩下了T[6]


16f28d5a55304007883f483e0010ecf6.png


  • 加入T[7], T[7] < T[6] 直接入栈,这就是最后的情况,result数组也更新完了。

70f9adbed1924b9289fba054d8fd1180.png

那result[6] , result[7]怎么没更新啊,元素也一直在栈里。

其实定义result数组的时候,就应该直接初始化为0,如果result没有更新,说明这个元素右面没有更大的了,也就是为0。


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

二刷

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> result(temperatures.size() , 0);
        stack<int> my_stack;
        my_stack.push(0);
        for(int i=1 ; i<temperatures.size();i++)
        {
            if(my_stack.size() != 0 && temperatures[i] > temperatures[my_stack.top()])
            {
                result[my_stack.top()] = i - my_stack.top();
                my_stack.pop();
            }
            my_stack.push(i);
        }
        return result;
    }
};

相关文章
|
2月前
|
C++
leetcode739 每日温度
leetcode739 每日温度
|
2月前
|
算法
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
31 3
|
2月前
|
存储 算法
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
30 1
|
2月前
|
索引
leetcode代码记录(每日温度
leetcode代码记录(每日温度
21 0
|
2月前
|
容器
代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I
代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I
47 0
|
2月前
|
SQL
leetcode-SQL-197. 上升的温度
leetcode-SQL-197. 上升的温度
23 0
|
2月前
|
索引
leetcode-739:每日温度
leetcode-739:每日温度
33 0
【LeetCode-每日一题】-739-每日温度
【LeetCode-每日一题】-739-每日温度
|
11月前
力扣739 每日温度
力扣739 每日温度
50 0
|
测试技术 数据库
LeetCode(数据库)- 上升的温度
LeetCode(数据库)- 上升的温度
123 0