单调栈和单调队列的模板题

发布时间:2024年01月11日

单调栈和单调队列的思想其实是类似的,是一种优化方式。

通过单调栈和单调队列,我们可以将原本O(n2)的问题优化到O(n)来做。

单调栈

题目

【模板】单调栈 - 洛谷

解题

单调栈的模板题

单调栈就是说,栈内元素始终存在单调性。我们通过维护一个单调栈,可以很容易求出数列中一个数前/后第一个比他大/小的数。

这是怎么实现的呢?

以本题为例,需要求出数列中第i个数后第一个比它大的数。

我们可以想象成,站在第i个位置上的人高度为x,他向右边看去,看到的第一个人就是我们要找的答案。于是,可以很容易地理解到,对于第i个位置上的人,他的右侧所有比他矮的人,都可以忽略。

体现在代码上,当a(cur)<a(i)&& cur>i时,a(cur)都不应该在栈里。

我们从右向左遍历数列,

①当栈不为空且栈顶元素小于a(i)时,使栈顶元素出栈;

②此时的栈顶元素就为对应的答案

③将当前元素加入答案数组

#include<iostream>
using namespace std;
const int N=3e6+10;
int q[N],tt=0;
int main()
{
    int n;
    cin>>n;
    int a[N],res[N];
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--)
    {
        while(tt&&a[q[tt]]<=a[i]) tt--;
        res[i]=q[tt];
        q[++tt]=i;
    }
    for(int i=1;i<=n;i++) cout<<res[i]<<" ";
}

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

单调队列

题目

活动 - AcWing

定滑动窗口位于每个位置时,窗口中的最大值和最小值。

解题

单调队列的模板题

单调队列和单调栈的思想一样,通过维护一个单调队列,我们可以很容易地得出某个滑动窗口内的最大/最小值。

我们的单调队列中只存下“有用”的元素。以求最小值为例,当前值大于队尾元素时,这个队尾元素就不可能是最小值了,当所有大于当前值的队尾元素都出队后,再将当前值入队,此时单调队列中的元素一定是单调的。

步骤为:

①判断队头元素是否需要出队

②将所有“无用”元素出队

③将当前元素入队

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6+10;
int n,k;
int q[N],hh=0,tt=-1;
int main()
{
    scanf("%d%d",&n,&k);
    int a[N];
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
    {
        if(tt-hh>=0&&i-k+1>q[hh]) hh++;
        while(tt-hh>=0&&a[i]<a[q[tt]]) tt--;
        q[++tt]=i;
        if(i>=k-1) cout<<a[q[hh]]<<" ";
    }
    cout<<endl;
    memset(q,0,sizeof(q));
    hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        if(tt-hh>=0&&i-k+1>q[hh]) hh++;
        while(tt-hh>=0&&a[i]>a[q[tt]]) tt--;
        q[++tt]=i;
        if(i>=k-1) cout<<a[q[hh]]<<" ";
    }
}

小tips

①栈和队列中存的都是下表

②判断是否出栈/队列时,要注意考虑等号的情况

文章来源:https://blog.csdn.net/weixin_68738523/article/details/135485814
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。