AcWing 154. 滑动窗口
原题链接
简单
作者:
szywdwd
,
2021-05-14 22:28:03
,
所有人可见
,
阅读 253
#include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N];// 队列保存数组元素的下标
int main()
{
int n, k;
cin >> n >> k;
for(int i = 0; i < n; ++i)
cin >> a[i];
int head = 0, tail = -1;
// 处理输出最小值的情况
for(int i = 0; i < n; ++i) {
// 如果移动滑窗右端点导致长度大于k, 就出队, 维持单调队列长度为k
if(head <= tail && i - k + 1 > q[head]) ++head;
// 若遇到的当前元素比队尾的小(维护的单调队列,从队头到队尾是递增的),则删除队尾元素,直到队列为空或遇到滑窗内最小的那个元素
// 这里难以理解,按代码流程模拟一边就好懂一点
while(head <= tail && a[q[tail]] >= a[i]) --tail;
// 当前元素入队尾
q[++tail] = i;
// 当从下标0开始,扫描过的元素足以达到滑窗大小时,即可输出滑窗内最大/最小值了,因为题目要求输出滑窗内的最值(长度必须为3)
if(i >= k - 1) cout << a[q[head]] << ' ';
}
cout << endl;
head = 0, tail = -1;
// 处理输出最大值的情况
for(int i = 0; i < n; ++i) {
if(head <= tail && i - k + 1 > q[head]) ++head;
while(head <= tail && a[q[tail]] <= a[i]) --tail;
q[++tail] = i;
if(i >= k - 1) cout << a[q[head]] << ' ';
}
return 0;
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH