题解 P1886 【滑动窗口】
这个就直接用单调队列来解决就好啦！
单调队列，即单调递减或单调递增的队列。
并且单调队列与普通队列的区别在于它既可以从队首出列，也可以从队尾出列。
那么我们应该怎样实现单调队列呢?
其实很简单，我们可以用某种叫做双端队列的东西。
双端队列的基本操作：
(1) deque<int> dq 定义一个int类型的双端队列dq(2) dq.push_back(x) 将x放入dq的末端
(3) dq.push_front(z) 将x放入dq的前端
(4) dq.pop_front() 弹出队列的前端元素
(5) dq.pop_back() 弹出队列的后端元素(6) dq.front() 返回队列的前端元素
(7) dq.back() 返回队列的后端元素之后这个，，题目的解法，，其实就很简单啦！！！
先从单调递增来说：
由于我们要找较小的那个数，所以放两个数同时在区间内的时候，下标较小并且数值较大的数就没有用了！！为了减少搜索次数，就重新开一个空间，放我们需要的数，把下标较小并且数值较大的数删去！！
接下来就是实现方法:
-
先让第一个数进队。
-
在下一个数进队之前， 进行判断：
1.在判断之前要看队列是否为空！！！如果空了它会找不到队首的数，那么就会报错！！
2.此时队首是否要删去。
3.队尾的数是否比下一个要推进队列里的数大。
-
将下一个数推进队列。
大概就是这样了
当输出的时候就要注意：
当推进去的个数没有到达k的时候，，不需要输出！！！
对了，差点忘了，，单增与单减的区别其实就是把大于号改成小于号就行啦
好啦下面就是代码：
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000005
int a[maxn];
int n,k;
struct node{//由于我们在判断队首是否需要删去的时候要利用下标，，所以开个结构体更加方便！
int pos,val;//pos就是下标了，val就是数值。
};
deque<node> b;
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++){//单调递增队列
if(!b.empty()&&i-b.front().pos>=k)
b.pop_front();
while(!b.empty()&&b.back().val>=a[i])
b.pop_back();
node t;t.pos=i;t.val=a[i];
b.push_back(t);
if(i>=k){
printf("%d ",b.front().val);
}
}
printf("\n");//别忘了这个哦
b.clear();//由于之前的队列中仍然还存在着数，，所以这里需要清空，当然啦，你再开一个双端队列也是可以的。
for(int i=1;i<=n;i++){//单调递减队列
if(!b.empty()&&i-b.front().pos>=k)
b.pop_front();
while(!b.empty()&&b.back().val<=a[i])
b.pop_back();
node t;t.pos=i;t.val=a[i];
b.push_back(t);
if(i>=k){
printf("%d ",b.front().val);
}
}
return 零;//你懂得！
}