単調キュースライド解除ウィンドウ-C++実装
転送ドア----スライドウィンドウ解析とC実装コード
#include
#include
using namespace std;
const int N = 1000000;
int n,k;
//
deque<int> min_v, max_v;
int a[N + 10];
int big[N+10];
int small[N + 10];
int arr = 1;
void input() {
cin >> n>>k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
}
void slidwindow() {
for (int i = 1; i <=n; i++)
{
// , , , ,
//
if (min_v.size() && k<=i-min_v.front()) {
min_v.pop_front();
}
if (max_v.size() && k <= i - max_v.front()) {
max_v.pop_front();
}
// ,
while(min_v.size() && a[min_v.back()]>=a[i]) {
min_v.pop_back();
}
while (max_v.size() && a[max_v.back()] <= a[i]) {
max_v.pop_back();
}
min_v.push_back(i);
max_v.push_back(i);
if (i>=k) {
big[arr] = a[max_v.front()];
small[arr] = a[min_v.front()];
arr++;
}
}
}
void output() {
for (int i = 1; i <arr; i++)
{
cout << small[i] << " ";
}
cout << endl;
for (int i = 1; i < arr; i++)
{
cout << big[i] << " ";
}
}
int main() {
input();
slidwindow();
output();
return 0;
}