Java教程

算法—单调栈小结

本文主要是介绍算法—单调栈小结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法—单调栈小结

前言

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

单调栈

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

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

例题

496. 下一个更大元素 I

给你两个 没有重复元素 的数组 nums1nums2 ,其中nums1nums2 的子集。

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

nums1 中数字 x 的下一个更大元素是指 xnums2 中对应位置的右边的第一个比 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]

分析:

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

image-20211013191206235

代码:

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;
    }
};
这篇关于算法—单调栈小结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!