滑动窗口 /【模板】单调队列【双端队列】
题目描述
有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is \([1,3,-1,-3,5,3,6,7]\), and \(k = 3\)。
输入格式
输入一共有两行，第一行有两个正整数 \(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\%\) 的数据，\(1 \le n \le 10^5\)；
对于 \(100\%\) 的数据，\(1\le k \le n \le 10^6\)，\(a_i \in [-2^{31},2^{31})\)。
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<cctype>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1e6+10;
const int M = 2e5+10;
int q[N],a[N],hh,tt;
void solve(){
int n,k;
cin >> n >> k;
int hh = 0,tt = -1; //相等时队列中有元素
for(int i = 1; i <= n; i ++ ){
cin >> a[i];
if(hh <= tt && i - q[hh] + 1 > k)hh ++;
while(hh <= tt && a[q[tt]] > a[i])tt --;
q[++tt] = i;
if(i >= k)cout << a[q[hh]] << " ";
}
cout << nl;
hh = 0,tt = -1;
for(int i = 1; i <= n; i ++ ){
if(hh <= tt && i - q[hh] + 1 > k)hh ++;
while(hh <= tt && a[q[tt]] < a[i])tt --;
q[++tt] = i;
if(i >= k)cout << a[q[hh]] << " ";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}
注意【代码相关】
-
为什么队列存的是数组的下标而不是数组的值？
原因：窗口长度i - q[hh] + 1而不是tt - hh + 1【队列元素在数组不一定连续】
如果i - q[hh] + 1 > k则hh ++出队 -
为什么维护窗口长度时注意队列非空，按上面代码顺序tt不会都大于hh吗？
原因：当窗口长度为1时一开始会误判导致hh始终大于tt,然后输出的值总是0 -
为什么不需要初始化队列数组，只需要初始化hh和tt？
原因：后面进入队列的数会覆盖掉前面的 -
为什么维护单调性是和队尾元素比较而不是队头元素呢？
原因：比如说，我们要维护一个单调递减的队列，如果比较队头的话，只能保证队头元素大于当前元素，假设当前队列已经是递减的，也不能保证队列中其他元素也大于当前元素，如果队列中有元素小于当前元素，而每次输出结果是队头元素，可能就造成结果错误；而如果比较队尾元素的话，假设当前队列已经是递减的，我们可以保证当前元素小于队尾元素，也就可以保证当前元素小于队头元素，从而继续维护单调递减的队列