代码随想Day58 | 739. 每日温度、496.下一个更大元素 I

今天开始单调栈，这是单调栈一篇扫盲题目，也是经典题。

单调栈可以用来解决找到左边或者右边的第一个比当前元素更大的元素，然后进行其他操作；本质是用空间换时间。

单调栈在这类题的具体作用就是记录遍历过的元素，和当前元素进行比较。如果单调栈从顶到底是递增的，找的元素是第一个比当前元素大的元素；如果从顶到底是递减的，找的是第一个比当前元素小的元素。

具体到本题来讲比较的情况如下：

1. 当前元素<栈顶元素：压入栈；

2. 当前元素==栈顶元素：压入栈；

3. 当前元素>栈顶元素：①记录距离：res[s.top()]=i-s.top()；②栈顶的元素已经赋值，弹出；③继续比较当前元素和栈顶元素；

详细代码如下：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> s;
        vector<int>res(temperatures.size(),0);
        s.push(0);
        for(int i=1;i<temperatures.size();i++)
        {
            if(temperatures[i]<=temperatures[s.top()])
            {
                s.push(i);
            }
            else
            {
                while(!s.empty()&&temperatures[i]>temperatures[s.top()]) //大于一直弹出
                {
                    res[s.top()]=i-s.top();
                    s.pop();
                }
                s.push(i);
            }
        }
        return res;
    }
};

496.下一个更大元素?I?

本题和?739.?每日温度 差不多，先遍历nums2，在栈内压入的元素还是下标，区别在于这道题要求输出的是第一个大于当前元素的元素，所以在记录结果的时候，需要用一个哈希表，来记录栈顶元素的第一个比其大的元素；然后再对num1遍历，赋值对应的哈希表中元素即可。

详细代码如下：

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        //用哈希表来进行搜索
        stack<int>s;
        unordered_map<int,int>map;
        s.push(0);
        for(int i=1;i<nums2.size();i++)
        {
            while(!s.empty()&&nums2[i]>nums2[s.top()])
            {
                map[nums2[s.top()]]=nums2[i];
                s.pop();
            }
            s.push(i);
        }
        vector<int>res(nums1.size(),-1);
        for(int i=0;i<nums1.size();i++)
        {
            if(map.find(nums1[i])!=map.end()) res[i]=map[nums1[i]];
        }
        return res;

    }
};