【算法】单调栈

我们可以维护一个栈结构，先将数组的首元素入栈，然后开始遍历这个数组，如果遍历到的数组元素比栈顶元素小，那么就入栈；如果相等，也入栈；当遍历到的数组元素比此时栈顶的元素大时，记录此时相隔的天数，然后将栈顶元素弹出，继续比较栈顶的元素和数组元素的大小，直到栈顶元素小于或者等于栈顶元素，此时将该数组元素入栈。然后接着遍历下一个数组元素，依次循环。

由于题目中求的是相隔的天数，所以我们不需要将数组元素入栈，只需入栈该元素的下标即可，这样就可以直接计算相隔的天数：数组元素对应的下标减去栈顶元素对应的下标，就是该栈顶元素与下一个更高温度相隔的天数。

图示：（以题目中的示例1为例）

可以发现，栈中的元素（下标对应的元素）始终保持单调递减（从栈底到栈顶），因此成为单调栈。

【代码】

代码语言：javascript

AI代码解释

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n=temperatures.size();
        vector<int> ans(n,0);
        stack<int> st;//存储下标
        st.push(0);
        for(int i=1;i<n;i++)
        {
            //遇到温度大于栈顶的，就一直出栈，保持递减性
            while(!st.empty()&&temperatures[st.top()]<temperatures[i])
            {
                int index=st.top();
                st.pop();
                ans[index]=i-index;
            }
            st.push(i);
        }
        return ans;
    }
};

时间复杂度O(N)，每个元素最多入栈依次。空间复杂度O(N)

二，下一个更大的元素I

题目链接：496. 下一个更大元素 I - 力扣（LeetCode）

【题目描述】

本题存在两个数组，nums1是nums2的子集，对于nums1数组的每个元素，求出这些元素在对应nums2数组中的下一个更大的元素。如果不存在，则为-1

【算法】单调栈

本题与上一题的思路一样，只不过加了一点要求。

求当前元素的下一个更大的元素，就需要维护一个单调栈（单调递减）。

本题还是求数组nums2上每个元素的下一个更大的元素是多少。所以还是在nums2数组上使用单调栈。和上题的过程一样，只不过在判断的时候，还需加上一个条件。

假设找到了当前栈顶的下一个更大元素k，还需判断栈顶元素是否在nums1中出现过，如果该元素在nums1中出现过，那么就将k记录在最终结果数组ans中，不过还需要保证和nums1数组的位置一一对应。

所以可以做下预处理工作，将数组nums1中的元素和下标使用哈希表保存起来。

初始化ans数组时，可以全部初始化为-1.

【代码】

代码语言：javascript

AI代码解释

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n=nums1.size();
        vector<int> ans(n,-1);
        unordered_map<int,int> hash;
        for(int i=0;i<n;i++)
        hash[nums1[i]]=i;
        
        stack<int> st;//单调递减
        st.push(0);
        for(int i=1;i<nums2.size();i++)
        {
            while(!st.empty()&&nums2[st.top()]<nums2[i])
            {
                //判断是否在nums1中出现过
                if(hash.count(nums2[st.top()])>0)
                {
                    //求出该元素在nums1中对应的下标
                    int index=hash[nums2[st.top()]];
                    //记录结果
                    ans[index]=nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }
};

三，下一个更大的元素II

题目链接：503. 下一个更大元素 II - 力扣（LeetCode）

【题目描述】

求一个数组nums每一个元素的下一个更大的数，该数组是循环数组，数组最后一个元素接下来的元素就是数组的第一个元素。

【算法】单调栈

求下一个更大的元素，单调栈（单调递减栈）。

大致的方向还是使用单调栈。本题的重点是：如何处理循环数组。

方法一：是将原数组nums在后面再拼接一份。然后使用单调栈求下一个更大的元素。

将两个nums数组拼接起来，使用单调栈求出每一个元素的下一个更大值，存储在ans数组中，然后将ans数组的大小减为一半。

代码语言：javascript

AI代码解释

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        //拼接两个数组
        vector<int> nums1(nums.begin(),nums.end());
        nums.insert(nums.begin(),nums1.begin(),nums1.end());
        vector<int> ans(nums.size(),-1);

        stack<int> st;//单调递减
        st.push(0);
        for(int i=1;i<nums.size();i++)
        {
            while(!st.empty()&&nums[st.top()]<nums[i])
            {
                ans[st.top()]=nums[i];
                st.pop();
            }
            st.push(i);
        }
        //将数组减为原来的一般
        ans.resize(nums.size()/2);
        return ans;
    }
};

方法二：也可以不用扩充数组，在遍历的时候模拟走两边nums即可。