154. 滑动窗口
注意q[N]数组记录的是a[N]数组的下标。
主要的思想和单调栈类似。
#include<iostream>
#include<queue>
using namespace std;
const int N=1000010;
int q[N],a[N];
int main(){
int n,k,x;
int hh=0,tt=-1;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<n;i++){
if(hh<=tt && i-k+1>q[hh])hh++;
while(hh<=tt && a[q[tt]]>=a[i])tt--;
q[++tt]=i;
if(i>=k-1)printf("%d ",a[q[hh]]);
}
puts("");
hh=0,tt=-1;
for(int i=0;i<n;i++){
if(hh<=tt && i-k+1>q[hh])hh++;
while(hh<=tt && a[q[tt]]<=a[i])tt--;
q[++tt]=i;
if(i>=k-1)printf("%d ",a[q[hh]]);
}
return 0;
}
使用deque代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int arr[N],n,k;
deque<int>q,q2;
int main(){
cin>>n>>k;
for(int i=0;i<n;i++)cin>>arr[i];
for(int i=0;i<n;i++){
if(q.size() && q.front()<i-k+1)q.pop_front();
while(q.size() && arr[q.back()]>=arr[i])q.pop_back();
q.push_back(i);
if(i>=k-1)cout<<arr[q.front()]<<" ";
}
cout<<endl;
q=q2;
for(int i=0;i<n;i++){
if(q.size() && q.front()<i-k+1)q.pop_front();
while(q.size() && arr[q.back()]<=arr[i])q.pop_back();
q.push_back(i);
if(i>=k-1)cout<<arr[q.front()]<<" ";
}
return 0;
}
