Sliding Window（poj 2823）

单调队列的典型应用啦！下面解题思路来自老师的讲义……

考虑求最大（最小类似）的情况，需要维护一个单调非递增的队列，每次取队首元素即为当前窗口的最大元素。

当处理新的元素时：

1.队首元素超出窗口范围，将其出队。

2.如果新元素不大于队尾元素，则直接入队尾（因为可能后面会出现比它大的元素）。

3.如果新元素大于队尾元素，则删除队尾元素。反复执行直至新元素不大于队尾元素，然后将新元素入队尾。

算法复杂度为O(n)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,k;
int arr[maxn];
deque<int>Qmin;
deque<int>Qmax;
int main()
{
    while(scanf("%d%d",&n,&k)==2)
    {
        Qmin.clear();
        Qmax.clear();
        for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
        for(int i=1;i<=n;i++)
        {
            while(!Qmin.empty()&&arr[Qmin.back()]>=arr[i])
                Qmin.pop_back();
            Qmin.push_back(i);
            if(i>=k)
            {
                if(Qmin.front()<=i-k)
                    Qmin.pop_front();
                if(i==n) printf("%d\n",arr[Qmin.front()]);
                else printf("%d ",arr[Qmin.front()]);
            }
        }
        for(int i=1;i<=n;i++)
        {
            while(!Qmax.empty()&&arr[Qmax.back()]<=arr[i])
                Qmax.pop_back();
            Qmax.push_back(i);
            if(i>=k)
            {
                if(Qmax.front()<=i-k)
                    Qmax.pop_front();
                if(i==n) printf("%d\n",arr[Qmax.front()]);
                else printf("%d ",arr[Qmax.front()]);
            }
        }
    }
    return 0;
}