生成窗口最大值数组

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main{

    // 双端队列始终维持一个前大后小的结构，随着窗口右移，队列前面的元素会失效
    // 维护队列：如果队尾对应的元素小，弹出不要；如果队尾对应元素大，就把新的数组的下标加进来，继续维护前大后小的结构
    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        LinkedList<Integer> qMax = new LinkedList<>();
        int[] result = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            // 如果队尾对应的元素比较小，就弹出队尾，直到队尾的位置所代表的值比当前值arr[i]大
            while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[i]) {
                qMax.pollLast();
            }
            qMax.addLast(i);

            // 检查队头下标是否过期，过期就把队头弹出
            if (qMax.peekFirst() == i - w) {
                qMax.pollFirst();
            }
            // 如果窗口出现了，就开始记录每个窗口的最大值
            if (i >= w - 1) {
                result[index++] = arr[qMax.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n;
        int w;
        String line;
        while ((line = br.readLine()) != null) {
            n = Integer.parseInt(line.split(" ")[0]);
            w = Integer.parseInt(line.split(" ")[1]);
            int[] data = new int[n];
            String[] inputHelp = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                data[i] = Integer.parseInt(inputHelp[i]);
            }
            int[] res = getMaxWindow(data,w);
            StringBuilder sb = new StringBuilder();
            for (int i : res){
                sb.append(i).append(" ");
            }
            System.out.println(sb);
        }
    }
}