标签：单调队列

题目内容

P2251

大意：给定一个长度为n的序列a，然后求序列q满足q_i=\min{ a_i,a_{i+1},\cdots,a_{i+m-1} }

解题思路

单调队列裸题。

解法和滑动窗口的类似

使用两种方法：

ST表：

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=1e6+5;
int f[maxn][21],n,m,lg[maxn];

int main()
{
    scanf("%d %d",&n,&m);
    lg[0]=-1,lg[1]=0;
    for(int i=2;i<=n;i++)
        lg[i]=lg[i/2]+1;
    for(int i=1;i<=n;i++)
        scanf("%d",&f[i][0]);
    for(int j=1;j<=20;j++)
        for(int i=1;i<=n;i++)
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    for(int i=1,j=m;j<=n;i++,j++)
    {
        int s=lg[j-i+1];
        printf("%d\n",min(f[i][s],f[j-(1<<s)+1][s]));
    }
    return 0;
}

单调队列：

#include <cstdio>
#include <deque>
using namespace std;

const int maxn=1e6+5;
deque<int> q;
int n,m,a[maxn];

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        if((!q.empty())&&q.front()<=i-m)
            q.pop_front();
        if(q.empty())
            q.push_back(i);
        else
        {
            while((!q.empty())&&a[q.back()]>=a[i])
                q.pop_back();
            q.push_back(i);
        }
        if(i>=m)
            printf("%d\n",a[q.front()]);
    }
    return 0;
}

于是得出结论ST表更好打代码量更少但是比单调队列慢

题目内容

P1886

有一个长为n的序列a，以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

解题思路

暴力1

O(nk)的方法很好想嘛，就是纯的暴力，当然结果就是TLE，代码不放了

暴力2——ST表

众所周知，这是一个RMQ问题，可以使用ST表来做。但是注意千万注意空间，因为这个序列是1e6级别的，如果给max和min单独开ST表的话会MLE，所以只能两次分别处理咯。O(n\log n)预处理，O(1)查询

代码：

#include <cmath>//懒得造log了就用自带的吧
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=1e6+5;
int n,k,f[21][maxn],a[maxn];

int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&f[0][i]);
    //这里开始先造一遍最小值的
    for(int j=1;j<=20;j++)
        for(int i=1;i<=n;i++)
            f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
    //查询，使用双指针对应左端和右端
    for(int i=1,j=k; j<=n; i++,j++)
    {
        int s=log2(j-i+1);//log2函数真香
        printf("%d ",min(f[s][i],f[s][j-(1<<s)+1]));
    }
    putchar('\n');//记得换行
    for(int j=1;j<=20;j++)//开始造最大值的，直接在上面开搞，不会出现问题，因为都会直接覆盖掉
        for(int i=1;i<=n;i++)
            f[j][i]=max(f[j-1][i],f[j-1][i+(1<<(j-1))]);
    for(int i=1,j=k; j<=n; i++,j++)
    {
        int s=log2(j-i+1);
        printf("%d ",max(f[s][i],f[s][j-(1<<s)+1]));
    }
    return 0;
}

正解：单调队列

单调队列，顾名思义就是满足单调性的队列

可以通过deque实现，因为我太菜所以调了一个下午

在含有pop的操作中一定记得判断队列是否为空否则就是RE

我这里实现的方法是存入数组的下标，方便判断什么时候pop_front。

代码：

#include <cstdio>
#include <deque>
using namespace std;

const int maxn = 1e6 + 5;
int n, k, a[maxn];
deque<int> q;

int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
    {
        while((!q.empty())&&q.front()<=i-k)
            q.pop_front();
        if (q.empty())
            q.push_back(i);
        else if (a[q.back()] >= a[i])
        {
            while ((!q.empty()) && a[q.back()] >= a[i])
                q.pop_back();
            q.push_back(i);
        }
        else
            q.push_back(i);
        if(i>=k)
            printf("%d ",a[q.front()]);
    }
    printf("\n");
    q.clear();//记得换行且清空队列
    for (int i = 1; i <= n; i++)
    {
        while((!q.empty())&&q.front()<=i-k)
            q.pop_front();
        if (q.empty())
            q.push_back(i);
        else if (a[q.back()] <= a[i])
        {
            while ((!q.empty()) && a[q.back()] <= a[i])
                q.pop_back();
            q.push_back(i);
        }
        else
            q.push_back(i);
        if(i>=k)
            printf("%d ",a[q.front()]);
    }
    return 0;
}