一. 问题背景

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

 解决这个问题的时候，在数据量很大的情况下会碰到超时的问题。所以就需要在算法上做出改变。这也就是这道题的重点：递增/递减队列。

二.问题分析

 所谓递增(递减)队列想要实现的就是队列中的元素是有序排列的。在一开始我们会想要直接利用STL库中的优先队列实现这个事情，但是问题在于我们难以进入到优先队列的中间进行操作，只能对头和尾进行操作，在面对这个题里面对于窗口长度的限制的时候很难完成任务，所以我们选择自己实现一个双端队列的递增(递减)队列结构。

　  这个结构模拟一个队列，front代表队列头，back代表队列尾，我们需要做的就是维护这个双端队列，保证队列的头部是我们想要的值，如果求窗口的最大值，就需要维护双端队列的头部是最大值。  在处理的过程中，需要注意:因为是对数组中的数字操作，为了实现判断数字是否在窗口之内，我们在队列中存储的是数字在数组中的索引(具体可看代码实现)

三.代码实现

/*结构体实现版本*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[20000];
//递减队列，找大元素
struct QueueUp {
	int window; //定义窗口
    int front, back;
    int val[20000]; 
    QueueUp(int w) {
    	window=w;    //初始化传入窗口大小
        front = 0;
        back = 0;
    }
    //x传入的是在num中的索引
    int push(int x) {
        int tmp = a[x];
        //删掉窗口外的元素
        while (front < back && x - val[front] >= window)
            front++;
        //删掉从末尾开始的小元素
        while (back>= front && tmp >= a[val[back]])  //只要是比队尾大就一直删除元素，直到它称为队头
            back--;
        val[++back] = x;  //注意这里是++back，back--之后现在back指向是back的前一个位置
        return val[front];  //返回队头元素，这里维护的队头元素最大
    }
};
//递增队列，找小元素  同上
struct QueueDown { 
	int window;
    int front, back;
    int val[20000];
    QueueDown(int w){
		window=w;
        front = back = 0;
    }
    //x传入的是在num中的索引
    int push(int x) {
        int tmp = a[x];
        while (front < back && x - val[front] >= window)
            front++;
        while (back>= front && tmp <= a[val[back]])
            back--;
        val[++back] = x;
        return val[front];
    }
};
int main()
{
    int n,k;
    cin >> n>>k;
    QueueDown down(k);
    QueueUp up(k);
    int count=0;
    for (int i =0; i < n; i++) {
        cin>>a[i];
        if(count++ >= k-1){   //if 是窗口初始大小，小于窗口大小的不存在就不打印
        cout<<"窗口最小值"<<"     "<<a[down.push(i)]<<endl;
        cout<<"窗口最大值"<<a[up.push(i)]<<endl;
    }
    else{ //未达到初始窗口大小不打印
    	a[down.push(i)];
    	a[up.push(i)];
	}
    }
    return 0;
}

/*函数实现版本*/
#include <bits/stdc++.h>
using namespace std;
 
const int SIZE=1000005;
 
void workmin();
void workmax();
int read();
void write(int x);
 
int q2[SIZE],q1[SIZE],a[SIZE],n,m,head,tail;
 
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	workmin();
	workmax();
	
	return 0;
}
 
void workmin()			//求最小值 
{
	int head=1,tail=0;
	for (int i=1;i<=n;i++){     // 和上述过程一样
		while (head<=tail && q1[head]+m<=i) head++;		//窗口滑过去的元素出队列
		while (head<=tail && a[q1[tail]]>a[i]) tail--;	//将新入队的元素插入单调队列 
		q1[++tail]=i;									//入队 
		if (i>=m) printf("%d ",a[q1[head]]);			//大于窗口大小则打印队首元素 
	}
	cout<<endl;
}
 
void workmax()			//求最大值，过程见上 
{
	int head=1,tail=0;
	for (int i=1;i<=n;i++){
		while (head<=tail && q2[head]+m<=i) head++;
		while (head<=tail && a[q2[tail]]<a[i]) tail--;
		q2[++tail]=i;
		if (i>=m) printf("%d ",a[q2[head]]);
	}
}

参考文章：https://blog.csdn.net/Nicholas_PZQ/article/details/78609853