AcWing 154. 滑动窗口
原题链接
简单
作者:
RealDish
,
2020-09-22 00:10:29
,
所有人可见
,
阅读 563
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N = 1000010;
int a[N];
deque<int>windowslide;
int n, k;
void findMin(){
windowslide.clear();
for(int i = 0; i < n; i++){
while( !windowslide.empty() && a[windowslide.back()] > a[i] )windowslide.pop_back();
while( !windowslide.empty() && i - windowslide.front() >= k )windowslide.pop_front();
windowslide.push_back(i);
if(i >= k - 1)cout << a[windowslide.front()] << ' ' ;
}
}
void findMax(){
windowslide.clear();
for(int i = 0; i < n; i++){
while( !windowslide.empty() && a[windowslide.back()] < a[i])windowslide.pop_back();
while( !windowslide.empty() && i - windowslide.front() >= k)windowslide.pop_front();
windowslide.push_back(i);
if(i >= k - 1)cout << a[windowslide.front()] << ' ';
}
}
int main(){
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i];
findMin();
cout << endl;
findMax();
}