题解 P2032 【扫描】

· · 题解 

/*此题是单调队列裸题
求最大值要保证队列单调非增，且队列覆盖长度不超过k
因此需要记录队首元素的位置，可以用一个变量来记录
本题的代码使用了两个数组，a记录元素，q用来模拟队列，
注意q中存放的不是元素大小而是元素位置 
*/ 
#include<cstdio>
#define MAXN 2000005
using namespace std;
int n, k, a[MAXN], q[MAXN], head = 1, tail;
//head指向队首，tail指向队尾，注意这里的初始化
int main()
{
    scanf("%d%d%d", &n, &k, &a[1]);
    q[++tail] = 1; //a元素入队，注意这里队列中存的是元素下标！
    for(int i = 2; i <= n; i++)
    {
        scanf("%d", &a[i]);
        while(head <= tail && a[i] > a[q[tail]]) tail--; //弹出队尾元素直到队列递减
        q[++tail] = i;
        if(i - q[head] == k) head++;       //队列长度超过k时队首出队 
        if(i >= k) printf("%d\n", a[q[head]]); //输出结果 
    }
    return 0;
}