洛谷P1886 滑动窗口

· · 个人记录

题目描述

现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is [1 3 -1 -3 5 3 6 7], and k = 3.

输入输出格式

输入格式：

输入一共有两行，第一行为n,k。

第二行为n个数(<INT_MAX).

输出格式：

输出共两行，第一行为每次窗口滑动的最小值

第二行为每次窗口滑动的最大值

输入输出样例

输入 8 3 1 3 -1 -3 5 3 6 7

输出 -1 -3 -3 -3 3 3

3 3 5 5 6 7

说明

50%的数据，n<=10^5

100%的数据，n<=10^6

solution

这道题解法两种ST表和单调队列

由于才学了单调队列而且单调队列快一点，所以我选择了单调队列

两个单调队列，一个单调递增，另一个单调递减

记录最大值和最小值。

如果是单调递增，则若出现一个值就把比他小的值全部弹掉，因为前面的值不能比他影响的更多，而且没有用了，而比他大的数发在他后面因为等到下一个窗口它可能就成为了最小值。

单调队列的速度比ST表，但适用范围更小

代码

#include<bits/stdc++.h>
#define now qmax[head] 
#define now1 qmin[head] 

using namespace std;

const int MAXN = 1000001;

inline int read()
{
    int f=1,x=0;
    char ch;
    do
    {
        ch=getchar();
        if(ch=='-') f=-1;
    }while(ch<'0'||ch>'9');
    do
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }while(ch>='0'&&ch<='9');
    return f*x;
}

int n;

int k;

int qmax[MAXN];

int qmin[MAXN];

int a[MAXN];

int head=1,tail=0;

int main()
{
    n=read();
    k=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }    

    for(int i=1;i<=n;i++)
    {
        while(a[i]<=a[qmin[tail]]&&head<=tail) tail--;
        tail++;
        qmin[tail]=i;
        while(now1<=i-k) head++;
        if(i>=k) cout<<a[now1]<<" ";  
    }
    cout<<endl;
    head=1,tail=0;
    for(int i=1;i<=n;i++)
    {
        while(a[i]>=a[qmax[tail]]&&head<=tail) tail--;
        tail++;
        qmax[tail]=i;
        while(now<=i-k) head++;
        if(i>=k) cout<<a[now]<<" ";  
    }

}