数据结构：单调队列

单调队列的作用，归纳成一句话就是不断读入元素，不时去掉元素，随时查询最值

应用的话就比较高级了，除了滑动窗口这个题目，还有动态规划的效率优化，当然还有别的以后再整理

单调队列由于要不断从两端进行队列操作，所以采用双端队列来实现

在此例中，所有的数据都是放在a数组中的，我们用一个p来表示a数组中某一个元素的下标，然后在单调队列中存下标即可

我们以维护单调递增队列举例

while(!q.empty()&&a[p]<=a[q.back()])  //维护单调队列 
            q.pop_back();
        q.push_back(p);

对于一个新的p,我们用a[p]和当前单调队列的最后一个位置的元素作比较，如果发现比新插入元素的大的，全部扔出去，因为我这个队列只维护单调增，只方便找最小值即可，大的没用

然而，对于一些过期的元素，虽然他们很小，我们还是要把它们扔掉才可以

while(!q.empty()&&q.front()<p-k+1)  //维持题意的区间长度 
            q.pop_front();  //移出出界的元素 

接下来根据题意输出队列中元素的值即可

由于我们是单调递增队列，维护的是最小值，那么队首元素就是最有用的

if(p>=k-1)  //元素进够k个后开始输出答案 
            cout<<a[q.front()]<<" ";
        p++; 

下面给出滑动窗口的完整实现

//aininot260
//不断读入元素，不时去掉元素，随时询问最值
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1000005;
int n,k;
int a[maxn];
deque<int> q;
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int p=0;
    while(p<n)
    {
        while(!q.empty()&&a[p]<=a[q.back()])  //维护单调队列 
            q.pop_back();
        q.push_back(p);
        while(!q.empty()&&q.front()<p-k+1)  //维持题意的区间长度 
            q.pop_front();  //移出出界的元素 
        if(p>=k-1)  //元素进够k个后开始输出答案 
            cout<<a[q.front()]<<" ";
        p++; 
    }
    cout<<endl;
    
    p=0;
    q.clear();
    while(p<n)
    {
        while(!q.empty()&&a[p]>=a[q.back()])  //维护单调队列 
            q.pop_back();
        q.push_back(p);
        while(!q.empty()&&q.front()<p-k+1)  //维持题意的区间长度 
            q.pop_front();  //移出出界的元素 
        if(p>=k-1)  //元素进够k个后开始输出答案 
            cout<<a[q.front()]<<" ";
        p++; 
    }
    cout<<endl;
    return 0;
}