题目描述
在一个包含n个元素的数组上，有一个长度为k的窗户在从左向右滑动。窗户每滑动到一个位置，我们都可以看到k个元素在窗户中。如下的例子所示，假设数组为 [1 3 -1 -3 5 3 6 7]，而k等于3:
窗户位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
对于窗户滑动过的每个位置，请给出窗户内k个元素的最小值和最大值。
输入
输入文件：window.in
输入的第一行包括两个整数n，k，n表示数组的长度，k表示窗户的长度。
接下来一行包括n个整数，表示这个n个元素的数组。
输出
输出文件：window.out
输出包含两行，每行包括n-k+1个整数，第一行表示窗户从左到右滑动过程中的最小值，第二行表示窗户从左到右滑动过程中的最大值。
输入样例
8 3
1 3 -1 -3 5 3 6 7
输出样例
-1 -3 -3 -3 3 3
3 3 5 5 6 7
数据范围
对于100%的数据，3<=n<=1000000，1<=k<=n，数组中的每个元素均在int范围内
题解
虽然是单调队列的模板题，还是让我暴露了一些操作上的问题。最好不要先把第一个元素加入队列，否则k=1的情况会被卡掉。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 1000005
using namespace std;
int n,m,a[MAXN];
int bq[MAXN],sq[MAXN];
int bg[MAXN],sm[MAXN],zz;
void init()
{
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
}
int t1=1,t2=1,w1,w2;
void work()
{
int i;
for(i=1;i<=n;i++)
{while(w1>=t1&&bq[t1]<=i-m) t1++;
while(w2>=t2&&sq[t2]<=i-m) t2++;
while(w1>=t1&&a[i]>=a[bq[w1]]) w1--;
while(w2>=t2&&a[i]<=a[sq[w2]]) w2--;
bq[++w1]=i;sq[++w2]=i;
if(i>=m)
{zz++; bg[zz]=a[bq[t1]]; sm[zz]=a[sq[t2]];}
}
for(i=1;i<=zz;i++) printf("%d ",sm[i]);
printf("\n");
for(i=1;i<=zz;i++) printf("%d ",bg[i]);
}
int main()
{
freopen("window.in","r",stdin);
freopen("window.out","w",stdout);
init(); work();
return 0;
}