算法|Day50 单调栈1

LeetCode 739- 每日温度

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目描述：给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

解题思路

1. 首先此题是让我们找当前气温后出现的比其气温大的最近的一天的差值，这样我们就会想到用单调栈来记录所有遍历过的温度。
2. 我们需要一个递增的栈，首先压入第一天也就是下标为0的那天的温度，栈顶一直保存当前最低的温度，如果遇到某天温度比其大，则一直循环弹出栈顶元素，并存入当前天与栈顶天差值存入到result中，直到栈顶元素大于当前天温度为止，将当前天下标入栈即可。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        st.push(0);
        //没有找到更高温度时就为0，全部初始化为0
        vector<int> result(temperatures.size(),0);
        for(int i=1;i<temperatures.size();i++){
            //当前温度 小于等于 栈顶温度时，直接将其入栈，保持栈顶为最小温度下标。
            if(temperatures[st.top()] >= temperatures[i]){
                st.push(i);
            }else {
                //当前温度 大于 栈顶温度时，弹出栈顶元素。
                while(!st.empty() && temperatures[st.top()] < temperatures[i]){
                    //记录该天后面最近一次高于该天温度的下标差值，作为result，记录完成就弹出
                    result[st.top()] = i-st.top();
                    st.pop();
                }
                //当所有小于当前天温度的天都被弹出时，将当前天压入即可
                st.push(i);
            }
        }
        return result;
    }
};

总结：

• 单调栈主要是思考栈是升序还是降序，以及栈中存储的内容。

LeetCode 496.下一个更大元素 I

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目描述：nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

解题思路

思路一：

将单调栈的操作用在nums2中，使用递增的单调栈，栈顶永远保持最小的元素，遇到比栈顶大的元素的时候就去nums1中找对应元素的下标，然后存入当前的比其大的值即可。

遍历数组2中的元素，并直接使用for循环来找是否在数组1中出现过。（时间复杂度高）

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int>result(nums1.size(),-1);
        stack<int> st;
        st.push(0);
        int tmp;//用来记录数组1中元素的下标
        for(int i=1;i<nums2.size();i++){
            //栈顶记录最小元素的值
            if(nums2[st.top()] >= nums2[i]){
                st.push(i);
            }else{
                //当有大元素出现时，弹出对应的小元素，并且在nums1中寻找对应的元素
                while(!st.empty() && nums2[st.top()] < nums2[i]){
                    //tmp设置为-1，默认表示没找到的状态。
                    tmp = -1;
                    //当前小元素在nums1中存储的下标。
                    for(int j=0;j<nums1.size();j++){
                        if(nums1[j] == nums2[st.top()]){
                            tmp = j;
                            break;
                        }
                    }
                    if(tmp != -1){//为-1说明没在数组1中找到对应的元素所以不操作
                    	//直接存储到往对应位置存储当前元素值，也就是距离最近的大于他的值。
                    	result[tmp] = nums2[i];
                    }
                    //不管在nums1中找没找到这个值，都要把他弹出。
                    st.pop();
                }
                //将小元素全部弹出后，可以压栈了。
                st.push(i);
            }
        }
        return result;
    }
};

思路二：

其他思路都和思路一相同，就是这个思路是用map做映射来快速找到nums2中元素是否在nums1中出现过。

// 版本一
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; // key:下标元素，value：下标
        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 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) { // 看map里是否存在这个元素
                        int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
                        result[index] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

总结：

• 关键是单调栈的栈的理解。