FC单调队列-154. 滑动窗口
作者:
小花猪
,
2023-03-20 14:52:19
,
所有人可见
,
阅读 169
154. 滑动窗口
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6+10;
int a[N], q[N];
int n, k;
int main(){
cin>>n>>k;
for(int i=0; i<n; i++) cin>>a[i];
//求最小值
int h = 0, t = -1;
for(int i=0; i<n; i++){
if(h<=t && i-k+1 > q[h]) h++;
//比当前a[i]大的数不断出栈
while(h<=t && a[q[t]]>=a[i]) t--;
q[++t] = i;//保证进栈的元素是最小的
if(i >= k-1) printf("%d ", a[q[h]]);
}
cout<<endl;
memset(q,0,sizeof q);
//求最大值
h = 0, t = -1;
for(int i=0; i<n; i++){
if(h<=t && i-k+1 > q[h]) h++;
while(h<=t && a[q[t]]<=a[i]) t--;
q[++t] = i;
if(i >= k-1) printf("%d ", a[q[h]]);
}
return 0;
}