附近最小(蓝桥杯模拟题2023)
解释
参考滑动窗口一题
#include<bits/stdc++.h>
using namespace std;
const int N = 2000010;
int f[N], q[N], p[N];
int main()
{
int n, k;
cin >> n;
for(int i = 1;i <= n;i++) cin >> f[i];
cin >> k;
int t = k * 2 + 1;
//继续开数给数组
for(int i = n + 1;i <= n + k;i++) f[i] = 0x3f3f3f3f;
//队列
//hh是队头,tt是队尾
int hh = 0, tt = -1;
for(int i = 1;i <= n + k;i++) {
//当队列不为空的同时呢,满足队列元素大于等于t,即2 * k + 1时,删除队头元素
if(hh <= tt && i - t + 1 > q[hh]) hh++;
//当队列不为空的同时呢,满足队列里面是单调递增的,不满足的话就删除队尾元素
while(hh <= tt && f[q[tt]] >= f[i]) tt--;
//添加新的元素进到队列里面
q[++tt] = i;
//满足队列里面的元素是 i - k >= 1 的,即找到一组解,输出答案
if(i - k - 1 >= 0) cout << f[q[hh]] << ' ';
}
return 0;
}