7483-滑动窗口

题目传送
因为单调队列是递增的，队头要么是当前区间中最大(或最小)，队尾是当前区间中最小(或最大)，所以它能解决移动区间最值,有人马上会想到，求移动区间最值用RMQ不也可以吗?(假设学过RMQ)
ST求RMQ的时间复杂度是$O(NlogN)$，如果$N={10}^7$，那么$O(NlogN)=23\ast {10}^7$，会超时。
这题的数据规模$N={10}^6$，用RMQ也能做，不过这里我们主要来体会单调队列的思想。
单调队列思考方式
因为所有的区间都是等长且连续的，所以我们只要维护单调队列就可以了，把区间内的元素排列成单调队列，取出队头元素。
以下是取区间最大值为例：

void dp_max()
{
	int head=1,tail=1;
	memset(q,0,sizeof(q));
	memset(pos,0,sizeof(pos));
	for(int i = 1; i <= n; ++i){
		while(head<=tail && i - pos[head] > k - 1) ++head; //维护区间，不符合的出队
		while(head<=tail && q[tail]<=a[i]) --tail; //维护单调性，求最大是递减，所以
		q[++tail] = a[i];
		pos[tail] = i;
		Fmax[i] = q[head]; //区间长度为k,右端点为i的最优解
	}	
}

有两点需要注意：
1.虽然是单调队列，可不是说队头就是最大的，队尾就是最小的。因为毕竟不是排序，为了维护单调性，小的可能出队列了。
2.取队头元素一定要在维护之后，比如说：来了一个比当前队列中所有元素都大的，那么队列会被清空，然后才会入队，这时候的队头才是当前区间的最大值。
取区间最小值就不贴出来了，模仿一下最大值的思路即可。
最后输出的时候，从第$k$~$n$，即每个区间的右端点。

 for(int i = k; i <= n; i++) cout << Fmin[i] << " "; cout << "\n";
 for(int i = k; i <= n; i++) cout << Fmax[i] << " "; cout << "\n";