AcWing 154. 《算法基础课》单调队列--滑动窗口
原题链接
简单
作者:
藕丝泥霸
,
2024-02-24 17:16:40
,
所有人可见
,
阅读 25
单调队列
思路
- 单调队列
- 当队头不在滑动窗口内部,队头元素出队
- 对于找滑动窗口最小值,当队尾元素>=当前元素,队尾元素出队
>=和>均可,区别在于
- 使用 >= 意味着如果队尾元素与新元素相等,也会将队尾元素弹出队列。这有助于保持队列的长度,只保留必要的元素。
- 使用 > 意味着仅当队尾元素小于新元素时,才会弹出队列。这可能会导致队列中存在多个值相同的元素。
静态数组模拟
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int arr[N];
int n,k;
int q[N];//单调队列,存储的是arr的索引,以便判断是否在滑动窗口内
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&arr[i]);
int front=0,back=-1;
for(int i=0;i<n;i++){
//队列存索引的好处:判断队头不在滑动窗口内,出队
if(back>=front && q[front]<i-k+1) front++;
//队尾比新元素大,出队
while(back>=front && arr[q[back]]>arr[i]) back--;
q[++back]=i;
if(i>=k-1) printf("%d ",arr[q[front]]);
}
printf("\n");
front=0,back=-1;
for(int i=0;i<n;i++){
if(back>=front && q[front]<i-k+1) front++;
while(back>=front && arr[q[back]]<arr[i]) back--;
q[++back]=i;
if(i>=k-1) printf("%d ",arr[q[front]]);
}
return 0;
}
双端队列
#include<iostream>
#include<cstdio>
#include<deque>
using namespace std;
const int N=1e6+10;
int arr[N];
int n,k;
deque<int> q;//单调队列,存储arr的下标,方便判断是否在滑动窗口内
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&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) printf("%d ",arr[q.front()]);
}
printf("\n");
q.clear();
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) printf("%d ",arr[q.front()]);
}
return 0;
}