【POJ 2823】【Luogu P1886】Sliding Window 滑动窗口

程序员振安技术 2022年11月17日

0 收藏 867 点赞 4,266 浏览 1102 个字

POJ 2823
Luogu P1886
【解题思路】
这是一个单调队列算法的经典题目，几乎学习单调队列的人都接触过这题。
利用单调队列算法求出每一个固定区间内的最（大/小）值。
以下以最大值为例：
将要进队的值如果比队尾大，那么意味着进队值比队尾的值更优，那么从尾部继续向前寻找，如果还是比前面的更优，那么就一直寻找。直到符合条件或者队列为空为止，接着进行进队操作。
如果队头已经不在区间内，那么队头出队。
对于本题来说，其实队头出队的操作不一定需要写while循环，其实使用if也是等价的。
while (i-b[head]+1>k && head<tail) head++;
if (b[tail]-b[head]+1>k) head++;
在这一题，这样的两句其实是等价的。
【解题反思】
1. 由于数据量非常非常大，一定要采用scanf和printf进行输入输出，否则可能超时。（使用的是POJ的数据）
2. 注意在寻找最值之前要把队列初始化。
【参考程序】

#include<iostream>
#include<cstdio>
using namespace std;
int n,k,a[1000005],b[1000001];
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int j=1;j<=n;j++) b[j]=1000004;//初始化，使之指向一个无穷大的数值
    a[1000004]=2147483647;//初始化
    int head=1,tail=1,i=1;
    while (i<=n)
    {
        while (a[i]<=a[b[tail]]&&tail>=head)
            tail--;
        //如果进队的值比当前队尾更优，那么队尾出队
        tail++;
        b[tail]=i;//进队
        if (b[tail]-b[head]+1>k)
            head++;//由于每一次进队只进一个
        if (i>=k)
            printf("%d ",a[b[head]]);//如果已经读入足够的数据，那么输出结果
        i++;
    }
    cout<<endl;
    head=1,tail=1,i=1;
    for (int j=1;j<=n;j++) b[j]=0;
    while (i<=n)//与上同理
    {
        while (a[i]>=a[b[tail]]&&tail>=head) tail--;
        tail++;
        b[tail]=i;
        if (b[tail]-b[head]+1>k) head++;
        if (i>=k) printf("%d ",a[b[head]]);
        i++;
    }
    return 0;
}