AcWing 000. 单调队列-滑动窗口模板
原题链接
简单
作者:
CqAq
,
2024-04-04 13:50:58
,
所有人可见
,
阅读 3
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1E6 + 9;
int n, a[N], k;
vector<int> mi, mx;
int q[N];
signed main(void){
cin >> n >> k;
for(int i = 1; i <= n; ++ i) cin >> a[i];
int hh = 1, tt = 0;
//单调增--最大值单调队列--滑动窗口
for(int i = 1; i <= n; ++ i){
while(hh <= tt && q[hh] < i - k + 1) hh ++;
while(hh <= tt && a[q[tt]] < a[i]) tt --;
q[++ tt] = i;
if(i - k + 1 >= 1) mx.push_back(a[q[hh]]);
}
//单调减--最小值单调队列--滑动窗口
hh = 1, tt = 0;
for(int i = 1; i <= n; ++ i){
while(hh <= tt && q[hh] < i - k + 1) hh ++;
while(hh <= tt && a[q[tt]] > a[i]) -- tt;
q[++ tt] = i;
if(i - k + 1 >= 1) mi.push_back(a[q[hh]]);
}
//输出
for(auto i : mi) cout << i << ' ';
cout << '\n';
for(auto i : mx) cout << i << ' ';
return 0;
}