算法理解
队列保存下标。求最小值时维护值递增，队首自然是当前窗口最小值；求最大值时维护值递减。每次先移除队尾劣势候选和队首过期下标，再放入当前位置。
- 复杂度：
O(n)。 - 注意：过期条件是
q.front() <= i - k，队中保存的是下标而不是值。
模板代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
vector<long long>a(n+1);
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
deque<int>dui;
for (int i=1;i<=n;i++)
{
while (!dui.empty()&&a[i]<=a[dui.back()])
{
dui.pop_back();
}
while (!dui.empty()&&dui.front()<=i-k)
{
dui.pop_front();
}
dui.push_back(i);
if (i>=k) cout<<a[dui.front()]<<' ';
}
cout<<endl;
dui.clear();
for (int i=1;i<=n;i++)
{
while (!dui.empty()&&a[i]>=a[dui.back()])
{
dui.pop_back();
}
while (!dui.empty()&&dui.front()<=i-k)
{
dui.pop_front();
}
dui.push_back(i);
if (i>=k) cout<<a[dui.front()]<<' ';
}
return 0;
}
//数组模拟单调队列
//#include <bits/stdc++.h>
//using namespace std;
//const int MAXN = 2000010;
//int q[MAXN];
//int head, tail;
//
//int main()
//{
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int n, k;
// cin >> n >> k;
// vector<long long> a(n + 1);
// for (int i = 1; i <= n; i++)
// {
// cin >> a[i];
// }
//
// // 求滑动窗口最小值
// head = 1, tail = 1;
// for (int i = 1; i <= n; i++)
// {
// // 队尾弹出比当前大的，维护递增单调队列
// while (head < tail && a[i] <= a[q[tail - 1]])
// tail--;
// // 队头超出窗口范围弹出
// while (head < tail && q[head] <= i - k)
// head++;
// q[tail++] = i;
// if (i >= k)
// cout << a[q[head]] << ' ';
// }
// cout << '\n';
//
// // 求滑动窗口最大值
// head = 1, tail = 1;
// for (int i = 1; i <= n; i++)
// {
// // 队尾弹出比当前小的，维护递减单调队列
// while (head < tail && a[i] >= a[q[tail - 1]])
// tail--;
// // 队头超出窗口范围弹出
// while (head < tail && q[head] <= i - k)
// head++;
// q[tail++] = i;
// if (i >= k)
// cout << a[q[head]] << ' ';
// }
// cout << '\n';
// return 0;
//}