http://poj.org/problem?id=2823

An array of size n ≤ 10^6 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards 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 the sliding window at each position.

题意：求每k个相邻的数中的最小和大值。

思路：用朴素的RMQ时间上貌似可以，但空间开不下。据说因为间隔固定，第二维可以省略，然后就可以了？

单调队列是最好的办法。对于求最小值，维护一个单调递增队列，因为如果一个数在另一个数之后而且还比它小，那前面的那个数就是没用的，每次要求的最小值就是队列首。这个单调队列里的元素最多是自己及之后的k个数。O（n）

最大值是一样的道理。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 1000000+1000
#define ll long long

int n,k,a[maxn];
deque<int> Q;

int main()
{
//	freopen("input.in","r",stdin);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	
	for(int i=1;i<=k;i++)
	{
		while(!Q.empty()&&a[Q.back()]>=a[i])Q.pop_back();
		Q.push_back(i);
	}
	cout<<a[Q.front()];
	for(int i=k+1;i<=n;i++)
	{
		if(Q.front()==i-k)Q.pop_front();
		while(!Q.empty()&&a[Q.back()]>=a[i])Q.pop_back();
		Q.push_back(i);
		cout<<" "<<a[Q.front()];
	}
	
	Q.clear();puts("");
	for(int i=1;i<=k;i++)
	{
		while(!Q.empty()&&a[Q.back()]<=a[i])Q.pop_back();
		Q.push_back(i);
	}
	cout<<a[Q.front()];
	for(int i=k+1;i<=n;i++)
	{
		if(Q.front()==i-k)Q.pop_front();
		while(!Q.empty()&&a[Q.back()]<=a[i])Q.pop_back();
		Q.push_back(i);
		cout<<" "<<a[Q.front()];
	}
	puts("");
	return 0;
}