题目描述

blablabla

样例

blablabla

算法1

Java 代码

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int N = 1000010;
    static int[] q = new int[N];  // 队列数组, 其中存放 arr的下标值
    static int[] nums = new int[N];
    static int hh = 0, tt = -1;  // tt指向栈顶元素

    public static void main(String[] args) throws IOException {
        String[] str = reader.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);
        String[] s = reader.readLine().split(" ");
        for (int i = 0; i < n; i++){
            nums[i] = Integer.parseInt(s[i]);
        }

        // min
        // Deque store index
        Deque<Integer> qMin = new ArrayDeque<Integer>();
        for (int i = 0; i < n; i++){
            while(!qMin.isEmpty() && qMin.peekFirst() < i-k+1){
                qMin.pollFirst();
            }
            while(!qMin.isEmpty() && nums[i] < nums[qMin.peekLast()]){
                qMin.pollLast();
            }
            qMin.add(i);

            if(i+1>=k){
                writer.write(nums[qMin.peekFirst()] + " ");
            }
        }
        writer.write("\n");

        // max
        Deque<Integer> qMax = new ArrayDeque<Integer>();
        for (int i = 0; i < n; i++){
            while(!qMax.isEmpty() && qMax.peekFirst() < i-k+1){
                qMax.pollFirst();
            }
            while(!qMax.isEmpty() && nums[i] > nums[qMax.peekLast()]){
                qMax.pollLast();
            }
            qMax.add(i);

            if(i+1>=k){
                writer.write(nums[qMax.peekFirst()] + " ");
            }
        }
        writer.write("\n");

        writer.flush();
        reader.close();
        writer.close();

    }
}