洛谷题单指南-常见优化技巧-P2032 扫描

原题链接：https://www.luogu.com.cn/problem/P2032

题意解读：求滑动窗口内的最大值，典型的单调队列应用。

解题思路：

单调队列的三部曲：

1、去头。已存入的元素个数超过k，则去头。注意队列里存的是元素下标，只需要用当前下标减去队头元素来判断即可。

2、去尾。根据单调队列的单调性，如果求最大值则递减，如果求最小值则递增，判断要入队的元素和队尾元素的关系，破坏单调性的队尾元素出队，保持单调性。

3、入队。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 2000005;

int n, k;
int a[N];
int q[N], l = 0, r = -1; //手写双端队列

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i <= n; i++)
    {
        while(l <= r && i - q[l] + 1 > k) l++; //去头
        while(l <= r && a[i] > a[q[r]]) r--; //去尾
        q[++r] = i; //入队

        if(i >= k) cout << a[q[l]] << "\n";
    }
    return 0;
}