Day58|Leetcode 739. 每日温度 Leetcode 496. 下一个更大元素 I

Leetcode 739. 每日温度

题目链接?739 每日温度

学习单调栈，首先要明白什么时候用到单调栈，通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

而针对于本题来说，单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。这里我们要使用递增循序（再强调一下是指从栈头到栈底的顺序），因为只有递增的时候，栈里要加入一个元素i的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

使用单调栈主要有三个判断条件。

• 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
• 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
• 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

把全过程模拟一遍就可以，在对照这三种情况，就可以理解本题，下面上代码：

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

Leetcode 496. 下一个更大元素 I

题目链接?496 下一个更大元素 I

本题目和上面的题目差不多，这里只不过是拆成了两个数组，所以我们这里需要一个哈希映射，来找存在于num1中的和nums2中遍历元素相等的下标，我们这里用unordered_map，还需要注意一个点就是unordered_map的性质：unordered_map::count()是C++中的内置方法，如果Map中存在具有给定键的值，则此函数返回1，否则返回0。

下面上代码：

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(),-1);
        if(nums1.size() == 0){
            return result;
        }
        unordered_map<int,int> umap;
        for(int i=0;i<nums1.size();i++){
            umap[nums1[i]] = i;//哈希映射，为了寻找在nums1中是否存在nums2中元素
        }
        st.push(0);
        for(int i=1;i<nums2.size();i++){
            if(nums2[i]<nums2[st.top()]){
                st.push(i);
            }else if(nums2[i] == nums2[st.top()]){
                st.push(i);
            }else{
                while(!st.empty()&&nums2[i]>nums2[st.top()]){
                    if(umap.count(nums2[st.top()]) == 1){
                       int  index = umap[nums2[st.top()]];
                        result[index] = nums2[i];
                    }
                   st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

end,补完了有点累