题意

• 给定长为n序列，给定窗口长度k，问所有长为k的区间的最大值和最小值

思路

• 单调队列
• 并维护一个队列（以最大值为例），此队列中，队头表示的是当前窗口内的最大值，其他的是可能成为最大值的候选
• 同时，当新入队的元素比之前的元素大的时候，就意味着小的元素再也不可能成为最大值(生命周期没有新入队的长)
• 最终，窗口的左界扫到队首的时候就以为着队首生命周期结束

AC代码

#include<bits/stdc++.h>
using namespace std;
int a[2020200];
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){scanf("%d",&a[i]);}
	deque<int>mx,mn;
	for(int l=0,r=0;l<n;l++){
		while(r-l+1<=k&&r<n){
			while(!mn.empty()&&mn.back()>a[r]){
				mn.pop_back();
			}
			mn.push_back(a[r]);
			r++;
		}
		if(r-l+1>k){
            printf("%d ",mn.front());
			if(a[l]==mn.front()){
				mn.pop_front();
			}
		}
	}
	printf("\n");
	//对于最大值，如果一个新增元素大于当前元素，当前元素就不可能再成为最大元素
	for(int l=0,r=0;l<n;l++){
		while(r-l+1<=k&&r<n){
			while(!mx.empty()&&mx.back()<a[r]){
				mx.pop_back();
			}
			mx.push_back(a[r]);
			r++;
		}
		if(r-l+1>k){
            printf("%d ",mx.front());
			if(a[l]==mx.front()){
				mx.pop_front();
			}
		}
	}
	
	return 0;
}

PS

• 写个双指针墨迹了半天，要想要窗口内有k个元素，最终窗口r-l+1会等于k+1，所以大于k的时候才做输出处理