P1886 滑动窗口 /【模板】单调队列

题目描述

有一个长为 $n$ 的序列 $a$ ，以及一个大小为 $k$ 的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值。

例如，对于序列 $[1, 3, - 1, - 3, 5, 3, 6, 7]$ 以及 $k = 3$ ，有如下过程：

$7]37\def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array}$

输入格式

输入一共有两行，第一行有两个正整数 $n, k$ ；
第二行有 $n$ 个整数，表示序列 $a$ 。

输出格式

输出共两行，第一行为每次窗口滑动的最小值；
第二行为每次窗口滑动的最大值。

输入输出样例 #1

输入 #1

8 3
1 3 -1 -3 5 3 6 7

输出 #1

-1 -3 -3 -3 3 3
3 3 5 5 6 7

说明/提示

【数据范围】
对于 $50%50\%$ 的数据， $\le n \le 10^5$ ；
对于 $100%100\%$ 的数据， $1≤k≤n≤1061\le k \le n \le 10^6$ ， $ai∈[−231,231)a_i \in [-2^{31},2^{31})$ 。

解析：

无法暴力T_T

暴力枚举的方式是进行 $n - k$ 次循环，每次查找长度为k的区间的最值。这样的算法的时间复杂度为 $O(n^2)$ ，无法通过本题。

单调队列

可以建立一个队列来维护这些数据。这个队列有一些特点就是：队列中的数都是原序列 $a$ 中数字 $a_i$ 的下标 $i$ ，队列随着窗口滑动而更新，保证队列中存的下标都处于当前窗口中。并且保持队首为窗口中最大数的下标。

如何实现

那么如何实现呢？假设我们找每个区间的最小值：将原序列中每个数 $a_i$ 作为一个元素依次进行如下操作：如果队列为空，直接将当前元素下标 $i$ 入队。当队列不为空时，在加入新元素之前，检查队尾数 $f$ 代表的原序列数 $a_f$ 是否小于 $a_i$ ，若小于，则将队尾数删除，多次判断，直到队尾数 $f$ 代表的原序列数 $a_f$ 大于 $a_i$ 或队列为空。然后将 $i$ 放入队尾。再检查队首数 $s$ ，若 $s$ 已在我们的区间外，则将队首删去。则每段区间的最大值就是操作完的队列的队首数 $s$ 表示的原序列数 $a_s$

正确性验证

那么为何这样实现是正确的呢？因为我们的操作都保证了队列中的数 $x$ 表示的 $a_x$ 一定是单调递减的，且 $a_s$ 一定是最大的，当 $a_s$ 不在序列后，队列中第二个数 $t$ ，一定满足 $t > s$ 。虽然 $t$ 与 $s$ 没有必然的数量关系，但是 $a_{(s+1)→(t-1)}<a_t<a_s$ ，也就是说只要 $a_t$ 还在序列， $a_t$ 一定就是最大值！

几个注意点

但是注意最小值并不是每次操作之后队尾 $f$ 表示的数 $a_f$ ，因为在之前的操作中可能存在最小值在队尾，而新判断的元素 $a_i>a_f$ 导致 $a_f$ 被出队， $i$ 入队，而 $a_i$ 并不是区间最小值。所以与求最大值相似，求最小值要条件相反地建一个单调队列。

由于开始时 $i < k$ ，队列的变化无法表达整个区间，等到 $\geq k$ 了，才可以表示第 $i - k + 1$ 个区间的最值。

代码实现

由于两端都有出队操作， $ST L$ 中的普通队列 $q u e u e$ 已经无法满足。所以用 $ST L$ 中另一个神奇的双端队列 $d e q u e$ 。

deque相关

deque介绍：

首尾都可插入和删除的队列为双端队列。

deque声明：

deque<元素类型> 名称; 例: deque dq;

deque在本题中可能用到的函数：

队列名.push_back(x); 把x插入队尾后
队列名.push_front(x); 把x插到队首
队列名.back(); 返回队尾元素
队列名.front(); 返回队首元素
队列名.pop_back(); 删除队尾元素
队列名.pop_front(); 删除队首元素
队列名.empty(); 判断双端队列是否空
队列名.clear(); 清空双端队列

CoDe

代码与解析基本相符，注释略。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[1000005];
int mn[1000005];
int mx[1000005];
deque<int>dq;
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){while(!dq.empty()&&i-dq.front()+1>k) dq.pop_front();while(!dq.empty()&&a[dq.back()]>a[i]) dq.pop_back();dq.push_back(i);if(i>=k){mn[i]=a[dq.front()];}}for(int i=k;i<=n;i++){cout<<mn[i]<<' ';}cout<<endl;dq.clear();for(int i=1;i<=n;i++){while(!dq.empty()&&i-dq.front()+1>k) dq.pop_front();while(!dq.empty()&&a[dq.back()]<a[i]) dq.pop_back();dq.push_back(i);if(i>=k){mx[i]=a[dq.front()];}}for(int i=k;i<=n;i++){cout<<mx[i]<<' ';}return 0;
}