单调栈 学习与启发思路

本文帮助明确单调栈所需判断重点 并进行分析 便于快速找到切入点

总结：在了解单调栈之后，能快速得出while循环条件的能力是关键

前提：B站 灵茶山艾府 单调栈细讲

注1：请观看该视频后 或 了解单调栈之后 -> 阅读该文章

注2：以下讲解均为从右向左遍历 从左向右暂请自行理解运用

引入1：LEETCODE 739.每日温度

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

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

目的：在某天找到某天之后更高的气温所需最小天数

将示例1进行可视化表示：

为方便叙述 下标从1开始

例如：

第八天(73)后 ， 没有气温更高 ， 天数为0 (ans[8]=0)

第七天(76)后 ， 没有气温更高 ， 天数为0 (ans[7]=0)

第六天(72)后 ， 经过1天(76)气温更高 ，天数为1 (ans[6]=7-6)

第五天(69)后 ， 经过1天(72)气温更高 ，天数为1 (ans[5]=6-5)

第四天(71)后 ， 经过2天(72)气温更高 ，天数为2 (ans[4]=6-4)

第三天(75)后 ， 经过4天(76)气温更高 ，天数为4 (ans[3]=7-3)

第二天(74)后 ， 经过1天(75)气温更高 ，天数为1 (ans[2]=3-2)

第一天(73)后 ， 经过1天(74)气温更高 ，天数为1 (ans[1]=2-1)

不难看出，若 某天 温度大于 该天后的某一天 ，该天 的前面任何一天都不会再选 该天后的某一天 ， 因为 该天 相对于 该天后的某一天 温度更高，且下标更靠前

类似于山的高度，在下标为6的位置从左向右看，只能看到下标为7的位置，下标为8的位置被下标为7的位置挡住了

因此满足：

1. 记录的数据都 从前开始向后放（先进） 直到 温度 不大于 之前所记录的温度（单调性）

2. 删除的数据(例如在下标为7的位置看下标为8的位置)也 从前开始向后遍历删除（后出） 直到 温度 不大于 之前所记录的温度（单调性）

可推得 -> 栈 且为 单调栈

代码分析 + 注释

  vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int>ans(temperatures.size(),0);//返回的vector
        stack<int>st;//单调栈
        for(int i=temperatures.size()-1;i>=0;i--){//从右向左遍历
            int t=temperatures[i];//取出当前温度值
            while(!st.empty() && temperatures[st.top()] <= t){
                //如果 栈非空 且 栈顶所在下标的温度 小于等于 当前温度值
                st.pop();
                //不满足我们所说的 {温度更高，且下标更靠前} 原则，该下标需要删除
            }
            if(!st.empty()){//只要栈不为空 就意味着有解 即存在 温度更高 的情况
                ans[i]=st.top()-i;//下标之差 为 天数
            }
            st.push(i);//无论如何该下标都需要进栈 为以后的数据读入进行判断
        }
        return ans;
    }

其中

while(!st.empty() && '''temperatures[st.top()] <= t''' <- 这个条件是需要我们进行快速分析找到的){
    st.pop();
}

引入2：LEETCODE 496.下一个更大元素I

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] 是如上所述的 下一个更大元素 。

示例 1:
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

通过分析 从右向左遍历 我们很快发现：

压入元素大于栈顶就把栈顶元素弹出 直到 元素小于栈顶 把该元素放至栈顶

立刻得出while条件：

//此时栈里存的是元素
while( !st.empty() && num > st.top() ){
    st.pop();
}

参考代码(无注释，用到map哈希)

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n=nums2.size();
        unordered_map<int,int>hashmap;
        stack<int>st;
        for(int i=n-1;i>=0;i--){
            int num=nums2[i];
            while( !st.empty() && num > st.top() ){
                st.pop();
            }
            if(!st.empty())hashmap[num]=st.top();
            else hashmap[num]=-1;
            st.push(num);
        }
        vector<int>ret(nums1.size());
        for(int i=0;i<nums1.size();i++){
            ret[i]=hashmap[nums1[i]];
        }
        return ret;
    }