题解 | Sliding Window

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int n,k;
vector<int> a(N,0);

void solve(){
	
	deque<int> dq_min,dq_max;
	vector<int> res_min,res_max; 
	
	for(int i=1;i<=n;i++){
		
		while(!dq_min.empty()&&a[i]<=a[dq_min.back()]){
			dq_min.pop_back();
		}
		dq_min.push_back(i);
		while(dq_min.front()<i-k+1){
			dq_min.pop_front();
		}
		
		while(!dq_max.empty()&&a[i]>=a[dq_max.back()]){
			dq_max.pop_back();
		}
		dq_max.push_back(i);
		while(dq_max.front()<i-k+1){
			dq_max.pop_front();
		}
		
		if(i>=k){
			res_min.push_back(dq_min.front());
			res_max.push_back(dq_max.front());
		}
		
	}
	
	for(int i:res_min){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	for(int i:res_max){
		cout<<a[i]<<" ";
	}
	
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>k;
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	solve();
	
    return 0;
}