代码随想录算法训练营第五十八天|LeetCode739 每日温度、LeetCode496 下一个更大的元素

739.每日温度

思路：一开始想到了两层for循环的暴力解法，没想到单调栈要干嘛，直接看题解。单调栈内存放数组索引，栈内顺序为数组值从小到大，因此栈顶的索引对应的数组值在栈内是最小的。遍历数组每个元素，如果当前元素大于栈顶的元素，直接将栈顶索引对应的result处赋值为循环当前索引i与栈顶元素st.top()的差值，然后将栈顶弹出，如果当前元素仍大于栈顶元素对应的数组值，重复上述操作。如果当前索引对应的数组值小于等于栈顶元素对应的数组值，将当前索引放入栈内。

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

496.下一个更大的元素

思路：这道题分了两个数组，但本质上还是利用单调栈寻找比当前元素大的最近的那个元素。因此先对nums2寻找每个元素后面对应的最近的比他大的元素值，因此建立unordered_map<int> m2. m2[nums2[st.top()]]=nums2[i].遍历完数组2后，建立与数组1长度相同的result，遍历数组1，在m2中寻找有没有和数组1相同的元素，如果有，在对应result的位置放入map[nums1[i]]的key值。

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

收获：

在做这种搜寻比当前元素大或小的最近元素的问题时，可以考虑利用单调栈，栈内存索引，栈内顺序为索引对应的元素递增或递减。如果搜比当前元素大的最近元素，栈内就是递减，反之递增。