poj2823 滑动窗口 http://poj.org/problem?id=2823
单调队列：队列里的元素都是单调的。普通队列只允许先进先出，单调队列在入队时先进行判断———入队后是否是单调的，如果是就直接入队，如果不是就先从尾部把使它不单调的元素弹出。
STL中有deque(双向队列)，即队列的两边都可以进出，可以非常简单的实现上述结构。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>  //单调队列
using namespace std; 
typedef long long ll;
const int maxn = 1e6 + 5;

struct Node
{
    int val;
    int pos;
};

Node node[maxn];
int resmax[maxn];
int resmin[maxn];

deque<Node> Q1,Q2;
//q1给最大值用，单调递减  q2给最小值用，单调增
int main() 
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        Q1.clear(); Q2.clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&node[i].val);
            node[i].pos=i;
            while(!Q1.empty()&&Q1.back().val<=node[i].val) //如果队尾元素小于等于当前元素，删除
                Q1.pop_back();
            Q1.push_back(node[i]);
            while(!Q2.empty()&&Q2.back().val>=node[i].val) //如果队尾元素大于等于当前元素，删除
                Q2.pop_back();
            Q2.push_back(node[i]);
            if(i-Q1.front().pos+1>k) Q1.pop_front();     //如果队列里的区间长度大于k，就把队首元素删除
            if(i-Q2.front().pos+1>k) Q2.pop_front();     ////如果队列里的区间长度大于k，就把队首元素删除
            if(i>=k)                //第k个元素开始记录
            {
                resmax[i-k+1]=Q1.front().val;
                resmin[i-k+1]=Q2.front().val;
            }
        }
        for(int i=1;i<=n-k;i++)
        printf("%d ",resmin[i]);
        printf("%d\n",resmin[n-k+1]);
        for(int i=1;i<=n-k;i++)
        printf("%d ",resmax[i]);
        printf("%d\n",resmax[n-k+1]);
    }
    return 0;
}