附近最小(蓝桥杯模拟题2023)

题目来源
https://www.lanqiao.cn/problems/2415/learning/?page=1&first_category_id=1&sort=students_count&name=%E9%99%84%E8%BF%91%E6%9C%80%E5%B0%8F

解释

参考滑动窗口一题

#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; 
}