【POJ 2823】Sliding Window（单调队列/堆）---饶文津

题意

给定n，k，求滑窗[i,i+k-1]在(1<=i<=n)的最大值最小值。

题解

单调队列或堆。 入队的条件是当前的进入了滑窗范围。 出队的条件是当前不在滑窗范围。

代码

我用堆写的，但是堆写错了个小地方，查了很久才发现。

#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define pii pair<int,int> #define mp(i,j) make_pair(i,j) #define N 1000006 using namespace std; int n,k; int a[N]; pii q[N]; int back; void push(pii a,int d){ q[++back]=a; for(int i=back;i>1&&(d?q[i]>q[i>>1]:q[i]<q[i>>1]);i>>=1) swap(q[i],q[i>>1]); } void pop(int d){ swap(q[1],q[back--]); for(int i=1;i<=(back>>1);){ if(d?q[i]>=max(q[i<<1],q[i<<1|1]):q[i]<=min(q[i<<1],q[i<<1|1]))return;//qaq if(((i<<1|1)>back)||(d?q[i<<1]>q[i<<1|1]:q[i<<1]<q[i<<1|1])){ swap(q[i<<1],q[i]); i<<=1; }else{ swap(q[i<<1|1],q[i]); i=(i<<1|1); } } } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(i<=k)push(mp(a[i],i),0); } for(int i=k;i<=n;i++){ printf("%d ",q[1].first); while(back&&q[1].second<=i-k+1)pop(0); push(mp(a[i+1],i+1),0); } puts(""); back=0; for(int i=1;i<=k;i++)push(mp(a[i],i),1); for(int i=k;i<=n;i++){ printf("%d ",q[1].first); while(back&&q[1].second<=i-k+1)pop(1); push(mp(a[i+1],i+1),1); } return 0; }

单调队列,写起来简单多了，而且也不会和手写堆一样容易出错。

#include <cstdio> #define N 1000006 using namespace std; int n,k; int a[N],b[N],q[N],head,tail; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ while(head<tail&&a[i]<q[tail-1])tail--; b[tail]=i; q[tail++]=a[i]; while(head<tail&&b[head]<i-k+1)head++; if(i>=k)printf("%d ",q[head]); } puts(""); tail=head=0; for(int i=1;i<=n;i++){ while(head<tail&&a[i]>q[tail-1])tail--; b[tail]=i; q[tail++]=a[i]; while(head<tail&&b[head]<i-k+1)head++; if(i>=k)printf("%d ",q[head]); } return 0; } ---来自腾讯云社区的---饶文津