题意
给定n，k，求滑窗[i,i k-1]在(1<=i<=n)的最大值最小值。
题解
单调队列或堆。 入队的条件是当前的进入了滑窗范围。 出队的条件是当前不在滑窗范围。
代码
我用堆写的，但是堆写错了个小地方，查了很久才发现。
代码语言：javascript复制#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;
}单调队列,写起来简单多了，而且也不会和手写堆一样容易出错。
代码语言：javascript复制#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;
}
