题目描述
滑动窗口
还是很不错的一道题目,值得多做几遍
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int q[N], h = 0, t = -1; // 注意:模拟队列初始化时t = -1
int main(){
int n, k;
cin >> n >> k;
for(int i = 0;i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++){
if(h <= t && k < i - q[h] + 1) //当队列非空 并且 队列元素个数大于窗口数
h++;
while(h <= t && a[q[t]] >= a[i]) //窗口中的要比新来的元素大于等于那就让它出来
t--;
q[++t] = i;
if(i + 1 >= k) //当窗口第一次满了时,就是开始输出的时候了
cout << a[q[h]] << " ";
}
cout << endl;
h = 0, t = -1;
for(int i = 0; i < n; i++){
if(h <= t && k < i - q[h] + 1) //当队列非空 并且 队列元素个数大于窗口数
h++;
while(h <= t && a[q[t]] <= a[i]) //窗口中的要比新来的元素小于等于那就让它出来
t--;
q[++t] = i;
if(i + 1 >= k) //当窗口第一次满了时,就是开始输出的时候了
cout << a[q[h]] << " ";
}
}