算法描述
刚进窗口视野内的元素都是“新事物”,“新事物必然战胜旧事物”,也就是说它是目前本窗口内存活时间最久的元素
那么如果题目要求输出窗口内最小值/最大值,在新事物之前的旧事物如果比新事物值大/小,就没有意义了
因为只要新事物在一天,就输出不着它,又因为新事物比它左边的所有旧事物寿命长,那就意味着旧事物剩下的全部生命周期内,都没有他们出头的机会了,所以就及时把这些没有意义的元素删去
采取这样的策略就会导致一个结果:队列变成了一个严格单调递增/递减的单调队列,那么我们每次要输出最小/最大值
的时候就直接输出Queue[front]队头元素即可,就省去了一维的搜索时间
没有采用循环队列的代码(速度快一些,但是空间复杂度O(n),能AC但是不推荐)
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
void PRT(int q[],int a[],int front,int rear){
while(front!=rear){
cout<<front<<","<<rear<<" "<<a[q[front]]<<" ",front=(front+1)%4;
}
cout<<endl;
}
int main(void){
int n,k;
cin>>n>>k;
int a[n+1];
memset(a,0,sizeof(a));
for(int i=0;i<n;i++) cin>>a[i];
int q[n+3];
//输出窗口内最小值
memset(q,0,sizeof(q));
//q[0]=0;//双端队列,队头、队尾均可出队 队列内元素是a[]的下标i,a[i]在q里面呈单调上升
int front=0,rear=0;//循环队列判空:if(front==rear) 判满:if((rear+1)%k==front)
//队列存下标而不是存数组元素本身就是为了判断窗口越界时方便 详情见本循环最后那条语句
for(int i=0;i<n;i++){//从a[0]入队遍历到a[n-1]入队
if(i>k-1&&q[front]<i-k+1) front++;//确保元素都在窗口内
while(front<rear&&a[i]<=a[q[rear-1]]) rear--;//1.队不空2.当前将要入队的a[i]比队尾元素小 同时满足这两个条件的时候 队尾元素出队
q[rear++]=i;//把a[i]的下标存入队列中
if(k<=i+1) cout<<a[q[front]]<<" ";//从第一次凑成窗口时开始输出
}
cout<<endl;
//输出窗口内最大值
memset(q,0,sizeof(q));
front=0,rear=0;
for(int i=0;i<n;i++){//从a[0]入队遍历到a[n-1]入队
if(i>k-1&&q[front]<i-k+1) front++;//确保元素都在窗口内
while(front<rear&&a[i]>=a[q[rear-1]]) rear--;//1.队不空2.当前将要入队的a[i]比队尾元素小 同时满足这两个条件的时候 队尾元素出队
q[rear++]=i;//把a[i]的下标存入队列中
if(k<=i+1) cout<<a[q[front]]<<" ";//从第一次凑成窗口时开始输出
}
}
采用循环队列的代码(时间久一丢丢,但是时间复杂度没有变化,会超时,但是空间复杂度仅为O(k),推荐)
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
void PRT(int q[],int a[],int front,int rear){
while(front!=rear){
cout<<front<<","<<rear<<" "<<a[q[front]]<<" ",front=(front+1)%4;
}
cout<<endl;
}
int main(void){
int n,k;
cin>>n>>k;
int a[n+1];
memset(a,0,sizeof(a));
for(int i=0;i<n;i++) cin>>a[i];
int q[k+2];
//输出窗口内最小值
memset(q,0,sizeof(q));
//q[0]=0;//双端队列,队头、队尾均可出队 队列内元素是a[]的下标i,a[i]在q里面呈单调上升
int front=0,rear=0;//循环队列判空:if(front==rear) 判满:if((rear+1)%k==front)
//队列存下标而不是存数组元素本身就是为了判断窗口越界时方便 详情见本循环最后那条语句
int rear_s;
for(int i=0;i<n;i++){//从a[1]入队遍历到a[n-1]入队
if(i>k-1&&q[front]<i-k+1) front=(front+1)%(k+1);//确保元素都在窗口内
rear_s=(rear+k)%(k+1);
while(front!=rear&&a[i]<=a[q[rear_s]]) rear=rear_s,rear_s=(rear+k)%(k+1);//1.队不空2.当前将要入队的a[i]比队尾元素小 同时满足这两个条件的时候 队尾元素出队
q[rear]=i,rear=(rear+1)%(k+1);//把a[i]的下标存入队列中
if(k<=i+1) cout<<a[q[front]]<<" ";//从第一次凑成窗口时开始输出
}
cout<<endl;
//输出窗口内最大值
memset(q,0,sizeof(q));
front=0,rear=0;
for(int i=0;i<n;i++){
if(i>k-1&&q[front]<i-k+1) front=(front+1)%(k+1);
rear_s=(rear+k)%(k+1);
while(front!=rear&&a[i]>=a[q[rear_s]]) rear=rear_s;
q[rear]=i,rear=(rear+1)%(k+1);
if(k<=i+1) cout<<a[q[front]]<<" ";
}
}
采用牺牲一格空间的循环队列技巧补充:
(详情参见《数据结构》严老师版本)
判空:front==rear
判满:(rear+1)%(k+1)==front
front往后移动一格:front=(front+1)%(k+1)
rear往后移动一格:rear=(rear+1)%(k+1)
rear往前移动一格:rear=(rear+k+1-1)%(k+1)