滑动窗口 单调队列

题目描述
给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，如下图：

你的任务是找出窗体在各个位置时的最大值和最小值。
输入描述:
第1行：两个整数N和K；
第2行：N个整数，表示数组的N个元素；
输出描述:
第一行为滑动窗口从左向右移动到每个位置时的最小值，每个数之间用一个空格分开；
第二行为滑动窗口从左向右移动到每个位置时的最大值，每个数之间用一个空格分开。

示例：
输入
8 3
1 3 -1 -3 5 3 6 7
输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
备注:
对于20%的数据，K≤N≤1000；
对于50%的数据，K≤N≤10^5；
对于100 %100%的数据，K≤N≤10^6。

最开始想的是挪动窗口时更新加入的值和删除的值，发现不可行，如果删除的值恰好是最值而且窗口内有多个向等的值就不行了,然后想干脆线段树吧,nlogn的时间复杂度还凑合，然后不幸的是超内存。。。看题解发现是单调队列，

假设求最值时，我们维护一个单调递增的队列，每次从队列尾部将当前值插入进去，而且我们要找窗口的最小值，插入位置后边的值都大于当前值，而且队列里面的值都在当前值右边，不会比当前值晚出队，所以这些值已经没用了，可以直接删去，队列内是单调递增的所以队头位置就是当前的最小值，需要输出的时候输出队头就可以了，但是还有一个问题，窗口长度一定为k，窗口之前的值要删掉，只要在输出之前判断队头元素是否在窗口内就可以，所以队列里面就不能存值了，而要存数组的下标，有了下标就可以找到具体的值还可以判断是否在窗口内，一举两得。
找最大值与上面是一样的，每个元素最多入队出队各一次，复杂度O(n)

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int n,k,a[N],dq[N],l,r;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		while(r>=l&&a[i]<a[dq[r]]) r--;//队列尾部大于ai的都可以删掉了，找到ai应该插入的位置
		dq[++r]=i;//下标插入队列
		while(dq[l]<=i-k) l++;//删除队首不在窗口内的元素，一个if应该就可以了，每次移动只删除一个元素，上上个删除的在上次已经删除了
		if(i>=k)//构成了完整的窗口可以输出了
			cout<<a[dq[l]]<<' ';
	}
	cout<<endl;
	l=r=0;
	for(int i=1;i<=n;i++)//完全同上
	{
		while(l<=r&&a[i]>=a[dq[r]]) r--;
		dq[++r]=i;
		while(dq[l]<=i-k) l++;
		if(i>=k) cout<<a[dq[l]]<<' ';
	}
	return 0;
}