AcWing 154. 滑动窗口
原题链接
简单
#include<iostream>
#include<deque>
using namespace std;
const int MAXN = 1e6+10;
int a[MAXN],mi[MAXN],ma[MAXN];
int N,K;
deque<int> q;
int main(){
cin >> N >> K;
for(int i = 0; i < N; i++) cin >> a[i];
for(int i = 0; i < N; i++){
if(i >= K){
if(q.size() && q.front() == i-K) q.pop_front();
}
while(q.size() && a[q.back()] > a[i]){
q.pop_back();
}
q.push_back(i);
mi[i] = a[q.front()];
}
for(int i = K-1; i < N; i++) cout << mi[i] << " ";
cout << endl;
while(q.size()) q.pop_back();
for(int i = 0; i < N; i++){
if(i >= K){
if(q.size() && q.front() == i-K) q.pop_front();
}
while(q.size() && a[q.back()] < a[i]){
q.pop_back();
}
q.push_back(i);
ma[i] = a[q.front()];
}
for(int i = K-1; i < N; i++) cout << ma[i] << " ";
return 0;
}