算法—单调栈小结

前言

在leetcode刷题的时候遇到了503. 下一个更大元素 II。一开始是使用暴力解法，会因为\(O(n^2)\)的时间复杂度而导致超时。看了题解之后了解了单调栈相关的知识，运用单调栈的方法可以在\(O(n)\)时间内解决这个问题。

单调栈

单调栈是在栈的FILO(先进后出)的特性在再额外添加一个特性：从栈顶到栈底的元素是严格递增或者递减的。

单调栈的一个优势就是线性的时间复杂度，所有的元素只会进栈一次，而且一旦出栈之后就不会再进来。单调栈可以解决类似下一个更大元素的问题。

例题

496. 下一个更大元素 I

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 :

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

分析：

根据题意，我们只需要将nums2的每一个元素，求出它右边的第一个更大的元素，将对应关系放入哈希表。再遍历nums1，根据哈希表找出答案。

我们怎么找出nums2的右边第一个最大的元素，就利用单调栈来完成。我们遇到一个新的nums2中的元素，我们判断栈顶元素是否小于这个元素。如果是，将栈顶元素出栈。如果不是，将这个元素成为新的栈顶。

代码：

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> mp;
        stack<int> stk;
        for(int i = 0; i < nums2.size(); ++i)
        {
            while(!stk.empty()&&stk.top()<nums2[i])
            {
                mp[stk.top()] = nums2[i];
                stk.pop();
            }
            stk.push(nums2[i]);
        }
        while(!stk.empty())
        {
            mp[stk.top()] = -1;
            stk.pop();
        }
        vector<int> ret;
        for(int i = 0; i < nums1.size(); ++i)
        {   
            ret.push_back(mp[nums1[i]]);
        }
        return ret;
    }
};

503. 下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

分析：

可以遍历一次数组，如果元素是单调递减的（则他们的「下一个更大元素」相同），我们就把这些元素保存，直到找到一个较大的元素；把该较大元素逐一跟保存了的元素比较，如果该元素更大，那么它就是前面元素的「下一个更大元素」。

代码：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> stk;
        for(int i = 0; i < 2*n; ++i)
        {
            while(!stk.empty()&&(nums[stk.top()] < nums[i%n]))
            {
                res[stk.top()] = nums[i%n];
                stk.pop();
            }
            stk.push(i%n);
        }
        return res;
    }
};

739. 每日温度

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

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

分析：

一开始的想法就是针对每个温度值向后搜索，直到找到比它大的数，这样的方法时间复杂度肯定较大。我们用单调栈优化这个过程，维护一个存储下标的单调栈，遍历温度数组，遇到一个新的温度判断是否小于栈顶的温度。如果是，将栈顶元素出栈。如果不是，将这个元素成为新的栈顶。

代码：

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