代码随想录算法训练营第五十七 | 739. 每日温度、 496.下一个更大元素 I、503.下一个更大元素II

## 739. 每日温度

这里是引用
https://programmercarl.com/0739.%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6.html
第一次接触单调栈，看完视频讲解之后思路很清晰，对单调栈能够解决的问题类型有大致了解

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> st;
        vector<int> result(T.size(),0);
        st.push(0); //st中存的是下标
        for(int i=1;i<T.size();i++) {
            if(T[i]<=T[st.top()])
                st.push(i);
            else{
                //首先要判断栈非空，要不就会报错
                while(!st.empty() && T[i]>T[st.top()]) {
                    result[st.top()] = i-st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;

    }
};

在这里插入图片描述

496.下一个更大元素 I

https://programmercarl.com/0496.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0I.html

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(),-1);
        unordered_map<int,int> umap;
        if(nums1.size()==0)
            return result;
        for(int i=0;i<nums1.size();i++) {
            umap[nums1[i]]=i;
        }
        st.push(0);
        for(int i=1;i<nums2.size();i++) {
            if(nums2[i] <= nums2[st.top()])
                st.push(i);
            else {
                while(!st.empty() && nums2[i]>nums2[st.top()]) {
                    if(umap.count(nums2[st.top()]) > 0) {
                        int index = umap[nums2[st.top()]];
                        result[index] = nums2[i];
                    }
                    st.pop();
                }
            st.push(i);
            }
        }
        return result;
    }
};

503.下一个更大元素II

https://programmercarl.com/0503.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0II.html

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> st;
        vector<int> nums1(nums.begin(),nums.end());
        nums.insert(nums.end(),nums1.begin(),nums1.end());
        //此时的nums的大小是原先的二倍
        vector<int> result(nums.size(),-1);
        if(nums.size()==0)
            return result;
        st.push(0);
        for(int i=1;i<nums.size();i++) {
            if(nums[i]<=nums[st.top()])
                st.push(i);
            else{
                while(!st.empty() && nums[i]>nums[st.top()]) {
                    result[st.top()] = nums[i];
                    st.pop();
                }
                st.push(i);
            }
        }
        result.resize(nums.size()/2);
        return result;
    }
};