AcWing 154. 滑动窗口
原题链接
简单
作者:
qpalzmczy
,
2024-04-06 17:01:37
,
所有人可见
,
阅读 1
154 滑动窗口 单调队列
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
const int N = 1e6 + 10;
int n, k, a[N];
int main()
{
scanf("%d%d",&n ,&k);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
deque<int> q;
// 最小值
for(int i = 1; i <= n; i++)
{
while(q.size() && q.back() > a[i]) q.pop_back();
q.push_back(a[i]);
// i为窗口右侧序号,如果窗口已经滑出,且进入足够的数
if(i - k >= 1 && q.front() == a[i - k]) q.pop_front();
if(i >= k) cout << q.front() <<" ";
}
q.clear();
cout << endl;
//最大值
for(int i = 1; i <= n; i++)
{
while(q.size() && q.back() < a[i]) q.pop_back();
q.push_back(a[i]);
if(i - k >= 1 && a[i - k] == q.front()) q.pop_front();
if(i >= k) cout << q.front() << " ";
}
return 0;
}