题目来源：http://poj.org/problem?id=2823
Time Limit: 12000MS
Memory Limit: 65536K
Total Submissions: 68259
Accepted: 19358
Case Time Limit: 5000MS
Description
An array of size n ≤ 106 isgiven to you. There is a sliding window of size k which ismoving from the very left of the array to the very right. You can only seethe knumbers in the window. Each time the sliding window movesrightwards by one position. Following is an example: The array is [1 3 -1 -3 5 3 6 7], and k is 3.
Window position
Minimum value
Maximum value
[1 3 -1] -3 5 3 6 7
-1
3
1 [3 -1 -3] 5 3 6 7
-3
3
1 3 [-1 -3 5] 3 6 7
-3
5
1 3 -1 [-3 5 3] 6 7
-3
5
1 3 -1 -3 [5 3 6] 7
3
6
1 3 -1 -3 5 [3 6 7]
3
7
Your task is to determine the maximum and minimum values in thesliding window at each position.
Input
The input consists of two lines. The first linecontains two integers n and k which are thelengths of the array and the sliding window. There are n integersin the second line.
Output
There are two lines in the output. The firstline gives the minimum values in the window at each position, from left toright, respectively. The second line gives the maximum values.
Sample Input
8 3 1 3 -1 -3 5 3 6 7SampleOutput
-1 -3 -3 -3 3 3 3 3 5 5 6 7Source
POJ Monthly--2006.04.28,Ikki
-----------------------------------------------------
思路
【题意】
经典的滑动窗口求最值问题。
给定n个数的序列，一长度为w的滑窗从左到右滑过整个序列，求这n-w+1个滑窗内的最大值和最小值。
【题解】
网上的题解有提到用线段树的，但我还不会线段树，就用单调队列做了。不加任何优化，在POJ上用C++提交可以5000ms左右AC，用G++提交会TLE. 算是低空飘过吧。
直接暴力的复杂度是O(nw), 而用单调队列可以降到O(n).
单调队列中的元素是结构体，结构体有2个属性：值和索引。单调队列（以单调下降队列为例）有如下性质：
1. 队列元素的值是严格单调下降的；
2. 队列元素的索引是严格单调上升的。
这样可以保证从队首开始第一个没有过期的元素的值就是当前窗口的最大值。
对于单调队列有2个操作：插入元素和查询第一个有效元素。
插入元素就是窗口滑入了一个新的元素，从队尾开始删除比小于等于新元素值的元素，直到队尾元素的值大于新元素，将新元素放到这个元素后面；如果新元素大于队首的值，则删除整个队列，新元素作为新队列。
查询第一个有效元素就是从队首开始找到第一个索引在当前窗口中有效的元素，并删除之前所有的过期元素。
对于单调递增队列同理。
由于所有元素入队一次出队一次，所以复杂度为O(n).
值得注意的是如果用C++ STL中的deque来做这个队列，用C++提交需要9000ms左右，如果用普通的数组自己实现双端队列的功能，用C++提交只需5000ms左右。
-----------------------------------------------------
代码
// 单调队列, 不用STL版, 用数组实现deque的功能 #include<fstream> #include<cstdio> using namespace std; struct node { int elem, index; node(void){} node(int ee, int ii): elem(ee), index(ii){} }; const int NMAX = 1000005; int a[NMAX] = {}; // 输入原始序列 node maxq[NMAX]; // 求最大值用单调递减队列, 用数组实现 node minq[NMAX]; // 求最小值用单调递增队列, 用数组实现 int maxv[NMAX] = {}; // 最大值结果序列 int minv[NMAX] = {}; // 最小值结果序列 int maxhead = 0, minhead = 0, maxtail = 0, mintail = 0; // 队列头/尾的下标 void append(node nd, bool up) // 将一个新元素elem加入长度为单调队列maxq或minq(up表示minq, !up表示maxq) { if (!up) { while (maxtail>=maxhead && nd.elem >= maxq[maxtail--].elem); if (maxtail>=maxhead || nd.elem < maxq[maxhead].elem) { maxtail += 2; maxq[maxtail] = nd; } else if (nd.elem >= maxq[maxhead].elem) { maxq[++maxtail] = nd; maxhead = maxtail; } } else { while (mintail>=minhead && nd.elem <= minq[mintail--].elem); if (mintail>=minhead || nd.elem > minq[minhead].elem) { mintail += 2; minq[mintail] = nd; } else if (nd.elem <= minq[minhead].elem) { minq[++mintail] = nd; minhead = mintail; } } } int gethead(bool up, int index, int w) // 当第index-w+1个窗口滑过时获取单调队列从队首开始第一个没有过期的元素(up表示minq, !up表示maxq) { if (!up) { while (maxq[maxhead++].index<index-w+1); return maxq[--maxhead].elem; } else { while (minq[minhead++].index<index-w+1); return minq[--minhead].elem; } } int main() { #ifndef ONLINE_JUDGE ifstream fin ("2823.txt"); int n,w,i; fin >> n >> w; for (i=0; i<n; i++) { fin >> a[i]; } fin.close(); for (i=0; i<w; i++) { if (i==0) { maxq[0] = node(a[0],0); minq[0] = node(a[0],0); } else { append(node(a[i],i), 0); append(node(a[i],i), 1); } } maxv[0] = maxq[0].elem; minv[0] = minq[0].elem; for (i=w; i<n; i++) { append(node(a[i],i), 0); append(node(a[i],i), 1); maxv[i-w+1] = gethead(0,i,w); minv[i-w+1] = gethead(1,i,w); } for (i=0; i<n-w+1; i++) { printf("%d ", minv[i]); } printf("\n"); for (i=0; i<n-w+1; i++) { printf("%d ", maxv[i]); } return 0; #endif #ifdef ONLINE_JUDGE int n,w,i; scanf("%d%d", &n, &w); for (i=0; i<n; i++) { scanf("%d", a+i); } for (i=0; i<w; i++) { if (i==0) { maxq[0] = node(a[0],0); minq[0] = node(a[0],0); } else { append(node(a[i],i), 0); append(node(a[i],i), 1); } } maxv[0] = maxq[0].elem; minv[0] = minq[0].elem; for (i=w; i<n; i++) { append(node(a[i],i), 0); append(node(a[i],i), 1); maxv[i-w+1] = gethead(0,i,w); minv[i-w+1] = gethead(1,i,w); } for (i=0; i<n-w+1; i++) { printf("%d ", minv[i]); } printf("\n"); for (i=0; i<n-w+1; i++) { printf("%d ", maxv[i]); } return 0; #endif }