AcWing 154. 滑动窗口 STL deque实现
原题链接
简单
作者:
Snrise
,
2024-03-30 19:54:39
,
所有人可见
,
阅读 1
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1000010;
deque<int> q;
int a[N];
int n, k;
signed main(void)
{
std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < n; i++)
{
if (q.size() && q.front() < i - k + 1)
{
q.pop_front();
}
while (q.size() && a[q.back()] >= a[i])
{
q.pop_back();
}
q.push_back(i);
if (i >= k - 1)
{
cout << a[q.front()] << ' ';
}
}
cout << endl;
q.clear();
for (int i = 0; i < n; i++)
{
if (q.size() && q.front() < i - k + 1)
{
q.pop_front();
}
while (q.size() && a[q.back()] <= a[i])
{
q.pop_back();
}
q.push_back(i);
if (i >= k - 1)
{
cout << a[q.front()] << ' ';
}
}
return 0;
}