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

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

通过单调栈和单调队列，我们可以将原本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

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

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