首先得讲一下单调队列，顾名思义，单调队列就是队列中的每个元素具有单调性，如果是单调递增队列，那么每个元素都是单调递增的，反正，亦然。
那么如何对单调队列进行操作呢？
是这样的：对于单调队列而言，队首和队尾都可以进行出队操作，但只有队尾能够进行入队操作。
至于如何来维护单调队列，这里以单调递增队列为例：
1、如果队列的长度是一定的，首先判断队首元素是否在规定范围内，如果不再，则队首指针向后移动。（至于如何来判断是否在制定范围内，一般而言，我们可以给每个元素设定一个入队的序号，这样就能够知道每个元素原来的顺序了）。
2、每次加入元素是，如果元素小于队尾元素且队列非空，则减小尾指针，队尾元素出队列，直到保持队列单调性为止。
题目链接：http://acm.fzu.edu.cn/problem.php?pid=1894
单调队列的入门题，我们给每个队列中的元素设定一个入队序号，并且设置一个变量来记录当前有多少人离开，这样我们可以维护一个单调递减队列，每次入队的时候，找当前元素适合的位置，每次出队列的时候，判断当前队首元素的入队序号与离开总入数的大小，如果小于等于，则说明当前队首元素应该已经在出队范围内，那么队首指针应该向后移动，直到找到元素的序号比当前离开的总人数大的那个元素，并且出队列。
1 /************************************************************************* 2 > File Name: fzu1894.cpp 3 > Author: syhjh 4 > Created Time: 2014年03月11日 星期二 08时55分28秒 5 ************************************************************************/ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <algorithm> 10 using namespace std; 11 12 const int MAXN = (1000000 + 10); 13 struct Node { 14 int val, num; 15 }; 16 17 Node que[MAXN]; 18 19 int main() 20 { 21 char s1[7], s2[7]; 22 int Case; 23 scanf("%d", &Case); 24 while (Case--) { 25 int head = 0, tail = -1, val; 26 int num = 0, level = 0; 27 scanf("%s", s1); 28 while (~scanf("%s", s1)) { 29 if (strcmp(s1, "END") == 0) { 30 break; 31 } 32 if (s1[0] == ‘C‘) { 33 scanf("%s %d", s2, &val); 34 //找到当前值适合插入的位置，并且将其后面的元素全部舍弃 35 while (head <= tail && que[tail].val <= val) tail--; 36 que[++tail].val = val; 37 que[tail].num = ++num; 38 } else if (s1[0] == ‘Q‘) { 39 //level记录了有多少个离开，因此我们要找的是队头元素进队列时的序号大于 40 //目前离开的总人数，这样才能够说明当前元素还在队列中 41 while (head <= tail && que[head].num <= level) { 42 head++; 43 } 44 if (tail < head) { 45 puts("-1"); 46 } else 47 printf("%d\n", que[head].val); 48 } else 49 level++; 50 } 51 } 52 return 0; 53 }
题目链接：http://poj.org/problem?id=2823
比较裸的单调队列，可以开两个队列来保存结果，一个单调递增来保存最小值，一个单调递减来保存最大值，每个元素入队列时都给一个入队编号，然后我们在判断的时候，只要判断当前元素的序号与队首元素的序号相差不大与K，则最值就是当前队首元素，否则，队首指针向后移动，直到找到一个符合条件的元素。
1 /************************************************************************* 2 > File Name: poj2823.cpp 3 > Author: syhjh 4 > Created Time: 2014年03月11日 星期二 09时45分04秒 5 ************************************************************************/ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <algorithm> 10 #include <vector> 11 using namespace std; 12 13 const int MAXN = (1000000 + 100); 14 struct Node { 15 int val, index; 16 }; 17 18 Node que1[MAXN], que2[MAXN]; 19 int N, K, M; 20 int num[MAXN]; 21 int ans1[MAXN], ans2[MAXN]; 22 23 void getSolve1() 24 { 25 int head = 0, tail = -1, len = K; 26 M = 0; 27 for (int i = 1; i <= N; i++) { 28 while (head <= tail && num[i] <= que1[tail].val) { 29 tail--; 30 } 31 que1[++tail].val = num[i]; 32 que1[tail].index = i; 33 if (i - len == 0) { 34 while (head <= tail && i - que1[head].index + 1 > K) { 35 head++; 36 } 37 ans1[++M] = que1[head].val; 38 len++; 39 } 40 } 41 } 42 43 void getSolve2() 44 { 45 int head = 0, tail = -1, len = K; 46 M = 0; 47 for (int i = 1; i <= N; i++) { 48 while (head <= tail && num[i] >= que2[tail].val) { 49 tail--; 50 } 51 que2[++tail].val = num[i]; 52 que2[tail].index = i; 53 if (i - len == 0) { 54 while (head <= tail && i - que2[head].index + 1 > K) { 55 head++; 56 } 57 ans2[++M] = que2[head].val; 58 len++; 59 } 60 } 61 } 62 63 int main() 64 { 65 while (~scanf("%d %d", &N, &K)) { 66 for (int i = 1; i <= N; i++) { 67 scanf("%d", &num[i]); 68 } 69 getSolve1(); 70 getSolve2(); 71 for (int i = 1; i <= M; i++) { 72 if (i == M) printf("%d\n", ans1[i]); 73 else printf("%d ", ans1[i]); 74 } 75 for (int i = 1; i <= M; i++) { 76 if (i == M) printf("%d\n", ans2[i]); 77 else printf("%d ", ans2[i]); 78 } 79 } 80 return 0; 81 }
原文：http://www.cnblogs.com/wally/p/3593224.html
