滑动窗口双指针(单调队列)-爱代码爱编程
https://ac.nowcoder.com/acm/contest/22669/M
题目描述
给一个长度为N的数组,一个长为K的滑动窗体从最左端移至最右端,你只能看到窗口中的K个数,每次窗体向右移动一位,如下图:
你的任务是找出窗体在各个位置时的最大值和最小值。
输入描述:
第1行:两个整数N和K; 第2行:N个整数,表示数组的N个元素(≤2×10^9);
输出描述:
第一行为滑动窗口从左向右移动到每个位置时的最小值,每个数之间用一个空格分开; 第二行为滑动窗口从左向右移动到每个位置时的最大值,每个数之间用一个空格分开。
示例1
输入
8 3 1 3 -1 -3 5 3 6 7
输出
-1 -3 -3 -3 3 3 3 3 5 5 6 7
备注:
对于20%的数据,K≤N≤1000; 对于50%的数据,K≤N≤10^5; 对于100%的数据,K≤N≤10^6。
双指针+单调队列(数组实现)
#include<bits/stdc++.h>
using namespace std;
int a[1000005],p[1000005]; //p数组实现单调队列,储存的是a数组的下标
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int hh=0,tt=-1; //双指针,hh指向单调队列头元素,tt指向单调队列末位元素
for(int i=1;i<=n;i++){
while(hh<=tt&&p[hh]<=i-k)hh++; //当头元素超出队列,hh+1,指向下一个元素
while(hh<=tt&&a[p[tt]]>=a[i])tt--; //维护单调递增,删去队列末尾大于即将插入元素的元素
p[++tt]=i; //入队
if(i>=k)cout<<a[p[hh]]<<' '; //从i=k时开始
}
cout<<endl;
hh=0,tt=-1; //同理
for(int i=1;i<=n;i++){
while(hh<=tt&&p[hh]<=i-k)hh++;
while(hh<=tt&&a[p[tt]]<=a[i])tt--;
p[++tt]=i;
if(i>=k)cout<<a[p[hh]]<<' ';
}
return 0;
}
自己写的shi码(vector+deque实现)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
vector<pair<int,int> >v; //开pair数组(忘了开两个数组,一个存下标)
for(int i=1;i<=n;i++){
int a;
cin>>a;
v.push_back(make_pair(i,a));
}
deque<pair<int,int> >q; //deque模拟单调队列(没必要的)
for(int i=0;i<k-1;i++){ //先放入k-1个元素(没想到当i>=k时输出)
if(q.empty())q.push_back(v[i]); //判空
else{
while(q.empty()==0&&q.back().second>=v[i].second)q.pop_back();
q.push_back(v[i]); //维护单调
}
}
for(int i=k;i<=n;i++){ //先维护单调,再插入尾部元素,再输出头部元素
if(!q.empty()&&q.front().first<i-k+1)q.pop_front();
if(q.empty())q.push_back(v[i]);
else{
while(q.empty()==0&&q.back().second>=v[i-1].second)q.pop_back();
q.push_back(v[i-1]);
}
cout<<q.front().second<<' ';
}
cout<<endl;
q.clear();
for(int i=0;i<k-1;i++){ //以下同理
if(q.empty())q.push_back(v[i]);
else{
while(q.empty()==0&&q.back().second<=v[i].second)q.pop_back();
q.push_back(v[i]);
}
}
for(int i=k;i<=n;i++){
if(!q.empty()&&q.front().first<i-k+1)q.pop_front();
if(q.empty())q.push_back(v[i]);
else{
while(q.empty()==0&&q.back().second<=v[i-1].second)q.pop_back();
q.push_back(v[i-1]);
}
cout<<q.front().second<<' ';
}
return 0;
}