算法

滑动窗口算法 $O(n)$

    队头       队尾
     hh          tt

队头队尾的边界值
[i-k+1,i]

in数组记录数据的下标，最多只有k个数据，用于模拟队列
每次加入新数据时就进行判断，去除不符合条件的数据，通过改变队尾tt–实现。

Java 代码

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter write = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] temp = read.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int k = Integer.parseInt(temp[1]);
        temp = read.readLine().split(" ");
        int[] num = new int[n];
        int[] in = new int[1000010];
        int hh=0,tt=-1;
        for(int i=0;i<n;i++) {
            num[i] = Integer.parseInt(temp[i]);
            if(hh <= tt && in[hh]<i-k+1) hh++;
            while(hh <= tt && num[in[tt]] >= num[i])tt--;
            in[++tt] = i;

            if(i >= k-1) {
                write.write(String.parse(num[in[hh]]).concat(" "));
            }
        }
        write.write('\n');
        in = new int[1000010];
        hh=0;tt=-1;
        for(int i=0;i<n;i++) {
            if(hh <=tt && in[hh]<i-k+1) hh++;
            while(hh<=tt && num[in[tt]] <= num[i])tt--;
            in[++tt] = i;
            if(i>=k-1) {
                write.write(String.valueOf(num[in[hh]]).concat(" "));
            }
        }
        write.flush();

        read.close();

        write.close();
    }
}

参考题解

https://www.acwing.com/solution/content/4763/