一个求滑动窗口问题的板子
需要传入一个数组,窗口大小,比较函数
特别的:greater为最小值窗口,less为最大值窗口,类似于sort排序
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct MQueue {
vector<T> ans;
template <class K>
MQueue(vector<T> &a, int k, const K cmp) {
ans.assign(a.size(), 0);
deque<int> que;
for (int i = 0; i < a.size(); ++ i) {
if (!que.empty() && i - que.front() >= k) {
que.pop_front();
}
while (!que.empty() && cmp(a[que.back()], a[i])) {
que.pop_back();
}
que.push_back(i);
if (i >= k - 1) {
ans[i] = a[que.front()];
}
}
}
T operator[] (const int x) const { return ans[x]; }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
MQueue<int> f(a, m, less<int>()), g(a, m, greater<int>());
for (int i = m - 1; i < n; ++ i) {
cout << g[i] << " \n"[i + 1 == n];
}
for (int i = m - 1; i < n; ++ i) {
cout << f[i] << " \n"[i + 1 == n];
}
return 0;
}