-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathslide_min.cpp
More file actions
31 lines (29 loc) · 740 Bytes
/
Copy pathslide_min.cpp
File metadata and controls
31 lines (29 loc) · 740 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include "header.hpp"
template<typename T>
vector<T> slide_min(const vector<T>& v, int k) {
deque<int> deq;
vector<T> ret;
for(int i=0; i<v.size(); i++) {
while(!deq.empty() && v[deq.back()] >= v[i]) deq.pop_back();
deq.push_back(i);
if(i-k+1 >= 0) {
ret.push_back(v[deq.front()]);
if(deq.front() == i-k+1) deq.pop_front();
}
}
return ret;
}
template<typename T>
vector<T> slide_max(const vector<T>& v, int k) {
deque<int> deq;
vector<T> ret;
for(int i=0; i<v.size(); i++) {
while(!deq.empty() && v[deq.back()] <= v[i]) deq.pop_back();
deq.push_back(i);
if(i-k+1 >= 0) {
ret.push_back(v[deq.front()]);
if(deq.front() == i-k+1) deq.pop_front();
}
}
return ret;
}