题目内容

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;
}
最后修改日期:2020年2月25日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。