题解 | 【模板】滑动窗口

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] nums = new int[n];
        int index = 0;
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            nums[index] = in.nextInt();
            index++;
        }
        // 单调队列在处理滑动窗口时有高效率
        // 双端队列：适合处理滑动状况这种需要移除队尾元素的情况
        Deque<Integer> dq = new LinkedList<>(); // 存储下标
        ArrayList<Integer> result = new ArrayList<>();
        // 维护一个单调递减序列
        for(int i = 0; i < n; i++){
            // 移除所有小于当前元素的队尾下标，维护最大值是队头元素
            while(!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]){
                dq.pollLast();
            }
            // 将当前元素下标入队
            dq.offerLast(i);
            if(dq.peekFirst() <= i - k){
                dq.pollFirst();
            }
            // 当窗口形成后，记录最大值
            if(i >= k - 1){
                result.add(nums[dq.peekFirst()]);
            }
        }
        for(int x : result){
            System.out.print(x + " ");
        }

    }
}