单调队列——滑动窗口
搞了半天终于弄懂了,注释写的挺详细的,希望对大家有所帮助0.0
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, k; //数组长度是n,滑动窗口的大小是k
vector<int> Max, Min; //分别用来存放滑动窗口中的最大值和最小值
int a[N], q[N]; //a[]为原数组,q[]为单调队列
int front = 0, tail = -1; //初始化头指针和尾指针
/*问题说明:
1.关于队列:(1)单调队列中的元素既可以队头出队,也可以从队尾出队;
(2)队列中存放的是数组的下标(数组下标从0开始),这样做的目的是方便判断队头何时出队
2.关于滑动窗口:滑动窗口中左端的下标是i-k+1,右端的下标就是i,也就是说,i牵引着滑动窗口的移动,
i-k+1<0时,说明滑动窗口还没有形成(滑动窗口下标>=0才能开始输出),故还没有最小值,
不输出;如果q[front]<i-k+1,说明队头已经出了滑动窗口,则将队头出队;
3.基本思想同单调栈,如果要维护最小值,则每当有新元素要入队时,判断他前面的所有数,只要比他大的都不
可能是答案,所以直接出队,直到碰见比他小的数时他才入队,最终每个窗口中的最小值就是队头
a[q[front]];
4.滑动窗口的大小始终是k,且单调队列中存放的下标对应的数一定是严格单调的;*/
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
//i每加1意味着滑动窗口往后移动一位,因此i++等同于滑动窗口向后移动,对每个窗口依次去找它里面的最值即可
for (int i = 0; i < n; i++)
{
//队列非空且队头元素已经滑出窗口,将队头元素出队
if (front <= tail && q[front] < i - k + 1) front++;
//队列非空且队尾元素不小于当前数组元素,队尾出队
while (front <= tail && a[q[tail]] >= a[i]) tail--;
//满足单调性后新元素(数组当前元素a[i])入队
q[++tail] = i;
//滑动窗口已经形成,故此时滑动窗口最左端的元素就是窗口中的最小值
if (i - k + 1 >= 0) Min.push_back(a[q[front]]);
}
front = 0, tail = -1;
for (int i = 0; i < n; i++) //求最大值同理,只需将判断符号改变即可,最大值仍然是队头元素
{
if (front <= tail && q[front] < i - k + 1) front++;
while (front <= tail && a[q[tail]] <= a[i]) tail--;
q[++tail] = i;
if (i - k + 1 >= 0) Max.push_back(a[q[front]]);
}
//输出滑动窗口的最大值和最小值
for (int i = 0; i < Min.size(); i++) cout << Min[i] << " ";
puts("");
for (int i = 0; i < Max.size(); i++) cout << Max[i] << " ";
puts("");
return 0;
}