对于单调队列有一定的问题
请教一下
有一个长为 n的序列 a,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。
对于这个问题,可以使用双端队列来维护窗口的最值。
对于每个元素,将其加入队尾。同时,如果队列长度大于窗口大小 k,则将队首元素弹出。
每次滑动窗口时,需要更新队列中的最大值和最小值。这可以通过维护两个指针来实现。一个指向当前窗口中最大值的位置,另一个指向当前窗口中最小值的位置。
每次滑动窗口时,需要更新这两个指针的位置。如果当前队首元素已经不在窗口中,则需要将其弹出队列。
这个算法的时间复杂度为 O(n)。
可参考下以下内容:
#include<iostream>
using namespace std;
int main(){
int n,k;
int a[1000];
cin>>n>>k; // 输入序列长度n以及窗口大小k
for(int i=0;i<n;i++)
cin>>a[i]; // 输入序列a的各个值
for(int i=0;i<=n-k;i++){
cout<<"当前窗口中的值:";
int max = -1;
int min = 99999;
for(int j=0;j<=k-1;j++){
cout<<a[i+j]<<" ";
if(a[i+j]>max) max = a[i+j];
if(a[i+j]<min) min = a[i+j];
}
cout<<endl<<"最大值:"<<max<<" 最小值:"<<min<<endl;
}
}
不知道你这个问题是否已经解决, 如果还没有解决的话: