如果用一般的思路每次查找O(k)的复杂度,总时间复杂度达到O(k(n-k)) 数据范围显然需要优化算法
所以选用易理解的单调队列,和普通队列不同的是,要进行两端删除和插入需要双指针,当然stl的deque(双端队列)就可以实现。
具体实现:比如说[2,1]这个序列,当1一直存在时,2在出窗口之前永远不可能成为最小的那个值,所以这个元素就是无用值,所以每次移动窗口删除队首元素,从右到左寻找单调队列中比刚入队元素大的值(因为刚入队那个元素值始终比他们小,所以最小值就不是这些值)
最大值反之亦然
例如有序列5,2,6,8,10
k = 3
滑动窗口 [5,2,6],8,3 --> 5,[2,6,8],3 --> 5,2,[6,8,3]
单调队列依次为 [2,6 ] [2,6,8] [2,3]
#include <bits/stdc++.h> #define ll long long int using namespace std; const ll maxn=1000010; ll q1[maxn];///储存位置 ll p1[maxn];///储存min队列 ll q2[maxn]; ll p2[maxn]; ll front=1;///头指针 ll rear=0;///尾指针 ll n,k; ll a[maxn]; int main() { cin>>n>>k; for (int i=1;i<=n;++i) cin>>a[i]; for (int j=1;j<=n;++j) //min { while (front<=rear&&q1[rear]>=a[j])///无用值出队 --rear; q1[++rear]=a[j];///入队 p1[rear]=j;///保存入队值的位置 while (p1[front]<=j-k)++front;///滑动 if (j>=k) cout<<q1[front]<<' '; } cout<<endl; front=1; rear=0; for (int j=1;j<=n;++j)//max { while (front<=rear&&q2[rear]<=a[j])///无用值出队 --rear; q2[++rear]=a[j];///入队 p2[rear]=j; while (p2[front]<=j-k)++front; if (j>=k) cout<<q2[front]<<' '; } cout<<endl; return 0; }