P1886 滑动窗口 /【模板】单调队列

P1886 滑动窗口 /【模板】单调队列

 

 做题思路：

 

 

 

 

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 1e6 + 10;
int n,k,a[maxn];
deque<int> dp; //双端队列，普通队列队尾无法删除

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
while(!dp.empty() && a[dp.back()] > a[i]) dp.pop_back();
while(!dp.empty() && i - dp.front() >= k) dp.pop_front();
dp.push_back(i);
if(i >= k) cout << a[dp.front()] << " ";
}
cout << endl;

dp.clear();
for(int i = 1; i <= n; i++){
while(!dp.empty() && a[dp.back()] < a[i]) dp.pop_back();
while(!dp.empty() && i - dp.front() >= k) dp.pop_front();
dp.push_back(i);
if(i >= k) cout << a[dp.front()] << " ";
}
return 0;
}