题目大意：给n个数，一个长度为k(k<n)的闭区间从0滑动到n，求滑动中区间的最大值序列和最小值序列。
最大值和最小值是类似的，在此以最大值为例分析。
数据结构要求：能保存最多k个元素，快速取得最大值，更新时删去“过期”元素和“不再有希望”的元素，安放新元素。
单调队列的基本概念百度百科讲得比较清楚了：http://baike.baidu.com/view/3771451.htm
我的大致思路是：
1. 每个元素存储为结构体，包含它的秩和值。维护最大长度为k的单调队列，保证所有元素的秩都在区间内，且从首到尾的元素，秩递增，值递减。
2. 读入前k个元素（不存在过期问题），安放每个元素c：从队尾开始往回找到第一个大于它的元素g，将c放到g后面，c成为新的队尾
3. 队首赋给最大值序列的第一个值。
4. 读入k~n-1的元素，每读入一个元素c:
（1）处理队首的过期元素（每次最多只可能是队首一个元素过期，因为队列长度不超过k，且秩是单调增的）
（2）安放c（方法同前k个元素）
（3）将新队首赋给最大值序列的下一个值
5. 输出最大值序列
想清楚了的话，代码还是比较好写的；队列没有封装，简单地用数组+首尾指针实现：
1 #include <cstdio>
2 #include <cstring>
3 using namespace std;
4
5 struct Node
6 {
7 int index;
8 int value;
9 };
10
11 Node max_q[2000002],min_q[2000002];
12 int max_res[1000002],min_res[1000002];
13 int front_max,front_min;//队首指针
14 int back_max,back_min;//队尾指针
15 int n,k,c;
16
17 int main()
18 {
19 //freopen("c.txt","r",stdin);
20 scanf("%d%d",&n,&k);
21 back_max=back_min=front_max=front_min=0;
22 scanf("%d",&c);
23 max_q[back_max].value=c;
24 min_q[back_min].value=c;
25 max_q[back_max].index=0;
26 min_q[back_min].index=0;//用第一个元素初始化
27 for(int j=1;j<k;j++)//前k个元素
28 {
29 scanf("%d",&c);
30 while(back_max>=0 && max_q[back_max].value<=c) back_max--;
31 max_q[++back_max].value=c;
32 max_q[back_max].index=j;
33
34 while(back_min>=0 && min_q[back_min].value>=c) back_min--;
35 min_q[++back_min].value=c;
36 min_q[back_min].index=j;
37
38 }
39 max_res[0]=max_q[0].value;//区间起始位置的最值
40 min_res[0]=min_q[0].value;
41
42 for(int j=k;j<n;j++)//下标为k到n-1的元素
43 {
44 scanf("%d",&c);
45 if(max_q[front_max].index==j-k) front_max++;
46 if(min_q[front_min].index==j-k) front_min++;
47
48 while(back_max>=front_max && max_q[back_max].value<=c) back_max--;
49 max_q[++back_max].value=c;
50 max_q[back_max].index=j;
51
52 while(back_min>=front_min && min_q[back_min].value>=c) back_min--;
53 min_q[++back_min].value=c;
54 min_q[back_min].index=j;
55
56 max_res[j-k+1]=max_q[front_max].value;//每读入一个元素，更新一次区间，得到一个最值
57 min_res[j-k+1]=min_q[front_min].value;
58 }
59
60 for(int j=0;j<n-k+1;j++)
61 printf("%d ",min_res[j]);
62 printf("\n");
63 for(int j=0;j<n-k+1;j++)
64 printf("%d ",max_res[j]);
65 printf("\n");
66 return 0;
67 }
OJ的结果是这样的（G++会超时，尚不明原因）：
最开始没有考虑过期的问题，考虑之后担心队列不够长，需不需要写成循环的；但稍加分析会发现，front指针后移只发生在删除队首过期元素时，最多只发生n-k次，那么数组开到2n就可以了。
由于是不循环的队列，只需front和back两个指针就可完成所有需要的操作。（之前因为和一个计数变量混用，并是在边界判断时WA了很多次）
把前k个元素和之后的元素分开处理是为了考虑方便，AC了之后试图把它们合并起来然后并是又WA了。。。看来有时候不必过于追求代码的简炼，初学还是清晰更重要。