力扣-单调栈-739 每日温度

思路和时间复杂度

1. 思路：要求找出第一个大的元素，因此从左往右找到比栈顶大的元素就收集结果并且更新栈，弹出栈顶，如果是小于等于栈的元素，就入栈，因为跟所求的元素没什么关系，此时栈内从栈顶到栈底是单调递增的
2. 时间复杂度：       

代码

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