AcWing 154. 滑动窗口 C++
原题链接
简单
作者:
张立斌
,
2019-10-25 20:22:52
,
所有人可见
,
阅读 907
代码
#include <deque>
#include <iostream>
using namespace std;
template <typename Iterator, typename Compare>
void printWindow(Iterator begin, Iterator end, int windowSize, Compare compare) {
deque<pair<int, int>> deque0;
int i = 0;
for (Iterator iter = begin; iter != end; ++iter, ++i) {
while (!deque0.empty() && deque0.front().first + windowSize <= i) {
deque0.pop_front();
}
while (!deque0.empty() && compare(deque0.back().second, *iter)) {
deque0.pop_back();
}
deque0.push_back({i, *iter});
if (i + 1 >= windowSize) {
printf("%d ", deque0.front().second);
}
}
puts("");
}
int main(void) {
int n, k, x;
scanf("%d %d", &n, &k);
deque<int> deque0;
for (int i = 0; i < n; ++i) {
scanf("%d", &x);
deque0.push_back(x);
}
printWindow(deque0.begin(), deque0.end(), k, greater_equal<int>());
printWindow(deque0.begin(), deque0.end(), k, less_equal<int>());
return 0;
}
厉害了!