题目描述

维护一个一维固定大小区间之间的最小值最大值

样例

blablabla

算法1

(队列) $O(n)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, k;
int a[N], q[N];

int main(){
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++ )
    scanf("%d", &a[i]);
    int tt = 0, hh = 1;
    for(int i = 1; i <= n; i++ ) {
        while(hh <= tt && q[hh] <= i - k) hh ++ ;//维护k大小的区间，队列内存的是下标
        while(hh <= tt && a[q[tt]] >= a[i]) tt -- ;//把不可能为答案的值删了
        q[ ++ tt] = i;//上三行完成维护一个大小hh到tt的队列
        if(i >= k)printf("%d ",a[q[hh]]);
    }
    puts("");

    tt = 0, hh = 1;
    for(int i = 1; i <= n; i++ ) {
        while(hh <= tt && q[hh] <= i - k) hh ++ ;
        while(hh <= tt && a[q[tt]] <= a[i]) tt -- ;//把>= 改<=求最大
        q[ ++ tt] = i;

        if(i >= k)printf("%d ",a[q[hh]]);
    }
    puts("");
    return 0;
}