题目描述
简单的滑动窗口。
两种解答方式
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N];//q[N]存的是数组下标
//暴力做法会超时,两个指针的方式。t++和h++ O(nm);
deque<int> p;
int main()
{
int tt = -1, hh=0;//hh队列头 tt队列尾
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
//deque
for(int i=0;i<n;i++)
{
if(!p.empty() && p.front()<i-k+1) p.pop_front(); //[i-k+1,1]为规定的区间
while(!p.empty() && a[p.back()]>=a[i]) p.pop_back();
p.push_back(i);
if(i>=k-1) cout<<a[p.front()]<<" ";
}
cout<<endl;
p.clear();
for(int i=0;i<n;i++)
{
if(!p.empty() && p.front()<i-k+1) p.pop_front();
while(!p.empty() && a[p.back()]<=a[i]) p.pop_back();
p.push_back(i);
if(i>=k-1) cout<<a[p.front()]<<" ";
}
//模拟
// for(int i=0;i<n;i++)
// {
// if(hh<=tt && q[hh]<i-k+1) hh++;
// while(hh<=tt && a[q[tt]]>=a[i]) tt--;
// q[++tt]=i;
// if(i>=k-1) cout<<a[q[hh]]<<" ";
// }
// cout<<endl;
// hh = 0,tt = -1;
// for(int i=0;i<n;i++)
// {
// if(hh<=tt && q[hh]<i-k+1) hh++;
// while(hh<=tt && a[q[tt]]<=a[i]) tt--;
// q[++tt]=i;
// if(i>=k-1) cout<<a[q[hh]]<<" ";
// }
return 0;
}