AcWing 154. 滑动窗口
原题链接
简单
作者:
Mahiro2211
,
2023-01-10 09:31:26
,
所有人可见
,
阅读 127
#include<iostream>
#include<deque>
using namespace std;
deque<int>mem;
const int N = 1e6;
int a[N];
int main(){
int n , k;
scanf("%d%d",&n,&k);
for(int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
for(int i = 1 ; i <= n ; i++){
while(!mem.empty()&&a[mem.back()] >= a[i]){
mem.pop_back();
}
mem.push_back(i);
if(i >= k){
while(!mem.empty() && mem.front() <= i - k){
mem.pop_front();
}
cout<<a[mem.front()]<<' ';
}
}
puts("");
while(!mem.empty()) mem.pop_front();//清空
for(int i = 1 ; i <= n ; i++){
while(!mem.empty() && a[mem.back()] <= a[i]){
mem.pop_back();
}
mem.push_back(i);
if(i >= k){
while(!mem.empty() && mem.front() <= i - k){
mem.pop_front();
}
cout<<a[mem.front()]<<' ';
}
}
return 0;
}