滑动窗口+单调队列 概念与例题（P1886 洛谷）

（广东工业大学ACM专题学习一）

滑动窗口

滑动窗口算法（也叫尺取）的概念其实很简单，很多情况下要结合更多知识来解题，比如单调队列。
什么是滑动窗口：在计算机网络中，滑动窗口算法是用来改善吞吐量的技术。在算法中则是维护一个由左右指针在字符串或数组中构成的窗口（窗口大小可变或固定），在窗口中进行的操作。

单调队列

也叫双端队列，简单来说就是通过不段入队和出队，保证队列元素是单调的。

专题学习一 滑动窗口
下面我们主要讲一下如何维护一个单调队列。
有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

输入格式
输入一共有两行，第一行有两个正整数 n,k。 第二行 n 个整数，表示序列 a。
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入：

8 3
1 3 -1 -3 5 3 6 7

输出：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

分析：
这道题是滑动窗口+单调队列的模板题。

我们知道只要每窗口移动一次，输出最值即可；那么我们怎么求每个窗口的最值呢？如果暴力的话，我们可以在窗口每移动一次就遍历整窗口寻找最值，但是每移动一次就遍历，相当于遍历窗口位置还要遍历窗口里面的元素，复杂度可想而知。

所以我们只知道滑动窗口是不足够的，这里我们还需要学习单调队列来解决。

(我们先看找最小值)
维护一个单调队列，这个队列的性质是从队头到队尾元素一定是递增的同时遍历数组，队列中的元素在数组中的下标一定是单调递增的（因为每次都从队尾进去），而队头就是最小元素。
每遍历一个元素就让他和队尾判断；如果这个元素比队尾元素大，说明如果元素入队队列依然可以保持单调；如果这个元素比队尾小，也就是说如果这个元素入队了，队列就不单调了，这里我们就要踢出队尾元素（换个说法：按照找最值的思维，如果队尾元素比加入元素还大，那么这个队尾元素就完全没有成为最小值的潜力了），同时，不要别忘记窗口大小是有限的，如果队头元素下标和队尾元素下标之差大于窗口大小，就要踢出队头元素。
接下来我们模拟一下样例。（队列以数组元素为元素，也可以下标为元素，这里不讲）

注意：图中红色X就是被踢除的元素。
注意：我们要等到i遍历到k（也就是窗口大小），才开始输出。
如图：
①遍历元素1，1入队，没有元素出队。
②遍历元素3，3大于队尾1，3入队，没有元素出队。
③遍历元素-1，-1小于队尾3，3出队，再次判断，-1小于新队尾1，1出队，-1入队。
④遍历元素-3，-3小于队尾-1，-1出队，-3入队。
⑤遍历元素5，5大于-3,5入队，没有元素出队。
以此类推，遍历到3时，3小于5，5出队，再次判断，3大于-3，3入队。
这个过程维护了一个单调的队列，但还不够。

我们看最后一行，如果按照上面的判断，6可以进队，但是认真看看样例，窗口大小是3，-3到6已结溢出窗口了，所以我们每次判断都要加一个窗口长度的维护。
新建一个队列，每次元素进队的同时，下标也进队。
这时候添加一个操作
①遍历元素1，1入队，(队头和队尾下标之差小于3)没有元素出队。
②遍历元素3，3大于队尾1，3入队，（队头和队尾下标之差小于3）没有元素出队。
③遍历元素-1，-1小于队尾3，3出队，再次判断，-1小于新队尾1，1出队，（队头和队尾下标之差小于3）-1入队。
④遍历元素-3，-3小于队尾-1，-1出队，-3入队（队头和队尾下标之差小于3）。
⑤遍历元素5，5大于-3,5入队，（队头和队尾下标之差小于3）没有元素出队。
以此类推，遍历到3时，3小于5，5出队，再次判断，3大于-3，3入队。
遍历到6,6入队，（队头和队尾下标之差等于3）踢出队头元素-3。
只要每次遍历都输出队头就能得到序列，最大值只要判断的时候换一个符号。
参考代码：

#include <iostream>//使用数组来模拟队列
using namespace std;
int a[1000002];
int q[1000002];
int x[1000002];
int q1[1000002];
int x1[1000002];
int head=1,tail=0;
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){//最小
        while(head<=tail && x[head]+k<=i)head++;//head右移代表踢出队头
        while(head<=tail && q[tail]>a[i])tail--;//tail左移代表踢出队尾
        q[++tail]=a[i];//队尾右移同时元素入队
        x[tail]=i;
        if(i>=k)printf("%d ",q[head]);
    }
    cout<<endl;
    for(int i=1;i<=n;i++){//最大
        while(head<=tail && x1[head]+k<=i)head++;
        while(head<=tail && q1[tail]<a[i])tail--;
        q1[++tail]=a[i];
        x1[tail]=i;
        if(i>=k)printf("%d ",q1[head]);
    }
}