739. Daily Temperatures.md

739. Daily Temperatures

思路

数组里每个元素的右边第一个比它大的元素，若找不到用0填充。典型的单调栈，关于单调栈我已经总结过了（戳我），这里不再赘述，直接给出代码。

时空复杂度均为O(N)

C++

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int>res(T.size(), 0);
        
        stack<int>mono_stk;
        for(int i = n - 1; i >= 0; i--){ // 反向遍历
            while(!mono_stk.empty() && T[i] >= T[mono_stk.top()]) 
                mono_stk.pop();
            if(!mono_stk.empty()) 
                res[i] = mono_stk.top() - i;
            mono_stk.push(i);
        }
        return res;
    }
};