AcWing 154. 滑动窗口
原题链接
简单
作者:
qiao
,
2022-03-14 21:07:16
,
所有人可见
,
阅读 152
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N], q[N], h, t = -1;
//注意:q中存的是下标,a中存的才为值
int main()
{
int n, k; cin >> n >> k;
for (int i = 0; i < n; i++)scanf("%d", &a[i]);
//递增队列(因为比队尾大的数都出队了,进而留在队里的一定比队尾小,因此为递增队列)
for (int i = 0; i < n; i++)
{
if (h <= t && q[h] < i - k + 1)h++;//如果队头存的下标(q[h])<窗口最左端(i-k+1),则令其出队(h++)
while (h <= t && a[i] <= a[q[t]])t--;//如果当前读入的值<=队尾存的下标所对应的值,则该值永远也不会用到,因此令其出队t--
q[++t] = i;//将读入的值加入队尾
if (i >= k - 1)printf("%d ", a[q[h]]);//读满窗口后,开始输出
}puts("");
h = 0, t = -1;
//递减队列
for (int i = 0; i < n; i++)
{
//用到下标
if (h <= t && q[h] < i - k + 1)h++;
//用到值
while (h <= t && a[i] >= a[q[t]])t--;
q[++t] = i;
if (i >= k - 1)printf("%d ", a[q[h]]);
}
}