AcWing 154. 滑动窗口
原题链接
简单
滑动窗口
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
// queue存放下标,a存放数值
int queue[N], head, tail;
void init() {
head = 0, tail = -1;
}
bool empty() {
return head > tail;
}
void enqueue(int x) {
queue[++tail] = x;
}
int pop_back() {
return queue[tail--];
}
int dequeue() {
return queue[head++];
}
int first() {
return queue[head];
}
int last() {
return queue[tail];
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
init();
for (int i = 0; i < n; i++) {
// 出队,队首始终是窗口最小值的下标,i - k + 1 是窗口最左端点的元素的下标
// i - k + 1 > first(),即是队首下标不在窗口中,应该出队
if (!empty() && i - k + 1 > first()) dequeue();
// 入队,要保证单调性,入队前先弹出那些数值大于等于当前元素的,从尾部弹出
while (!empty() && a[last()] >= a[i]) pop_back();
enqueue(i);
// 窗口最左端点的元素的下标 > 0时,输出最小值
if (i - k + 1 > 0) printf("%d ", a[first()]);
}
puts("");
init();
for (int i = 0; i < n; i++) {
if (!empty() && i - k + 1 > first()) dequeue();
while (!empty() && a[last()] <= a[i]) pop_back();
enqueue(i);
if (i >= k - 1) printf("%d ", a[first()]);
}
puts("");
return 0;
}