题目描述

模板题
java不用快读会TLE

样例

import java.util.*;

public class Main {

    static int N = 1000010;

    static int[] a = new int[N];

    //队列里面存储的是数的下标
    static int[] q = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        //找最小值，形成一个单调递增的队列
        int hh = 0,tt = -1;
        for (int i = 0; i < n; i++) {

            //判断队头是否已经滑出窗口
            if (hh <= tt && i - k + 1 > q[hh]) {
               hh++;
            }

            //插入的数比队尾的数还小 队尾的数出队
            while (hh <= tt && a[q[tt]] >= a[i]) {
               //出队
               tt--;
            }
            //队尾插入数据
            q[++tt] = i;

            //当我们的数字不足k个就不用输出了
            if (i >= k - 1) {
                System.out.print(a[q[hh]] + " ");
            }
        }

        System.out.println();

        //找最大值，形成一个单调递减的队列
        hh = 0;tt = -1;
        for (int i = 0; i < n; i++) {

            //判断队头是否已经滑出窗口
            if (hh <= tt && i - k + 1 > q[hh]) {
               hh++;
            }

            //插入的数比队尾的数还大 队尾的数出队
            while (hh <= tt && a[q[tt]] <= a[i]) {
               //出队
               tt--;
            }
            //队尾插入数据
            q[++tt] = i;

            //当我们的数字不足k个就不用输出了
            if (i >= k - 1) {
                System.out.print(a[q[hh]] + " ");
            }
        }

    }
}