算法解析
简而言之,滑动窗口算法在一个特定大小的字符串或数组上进行操作,
而不在整个字符串和数组上操作,这样就降低了问题的复杂度,从而也
达到降低了循环的嵌套深度。其实这里就可以看出来滑动窗口主要应用
在数组和字符串上。
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
模型1->滑动窗口
相关例题->
154. 滑动窗口
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int q[N];
int p[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)cin>>q[i];
int hh=0,tt=-1;
for(int i=0;i<n;i++){
//维护步骤1:如果队列首脱离 以i为末端元素且区间为d的区域则被去除
if(i-m>=p[hh])hh++;
//维护步骤2:一旦发生位置冲突便将被顶掉(图示如下)
while(hh<=tt && q[i]<q[p[tt]])tt--;
p[++tt]=i;
if(i-m+1>=0)cout<<q[p[hh]]<<" ";
}
cout<<endl;
hh=0,tt=-1;
memset(p,0,sizeof p);
for(int i=0;i<n;i++){
if(i>=p[hh]+m)hh++;
while(hh<=tt && q[p[tt]]<q[i])tt--;
p[++tt]=i;
if(i-m+1>=0)cout<<q[p[hh]]<<" ";
}
return 0;
}
相关例题->
1238. 日志统计
===>动态维护一个长度为d的区间即可(相比于上一题不用去维护队列的性质)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
unordered_map<int,vector<int>> mp;
vector<int>ans;
int cnt[N];
bool st[N];
int n,d,k;
int main(){
cin>>n>>d>>k;
for(int i=0;i<n;i++){
int t,num;
cin>>t>>num;
mp[t].push_back(num);
}
int hh=1;
for(int i=1;i<=1e5+10;i++){
if(i-d>=hh){
for(auto it:mp[hh])cnt[it]--;
hh++;
}
for(auto it:mp[i]){
cnt[it]++;
if(cnt[it]>=k && !st[it]){
st[it]=true;
ans.push_back(it);
}
}
}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)cout<<ans[i]<<endl;
return 0;
}