生成滑动窗口的最大值数组

package com.chanmufeng.codingInterviewGuide.stackAndQueue_10;

import java.util.LinkedList;

/**
 * 生成窗口的最大值数组
 */
public class MaxWindow {
    /**
     * @param arr 给定数组
     * @param w   窗口长度
     * @return
     */
    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || arr.length < w || w < 1) {
            return null;
        }

        int len = arr.length;
        int[] res = new int[len - w + 1];
        LinkedList<Integer> qmax = new LinkedList<>();
        int index = 0;
        for (int i = 0; i < len; i++) {
            while (!qmax.isEmpty() && arr[i] >= arr[qmax.peekLast()]) {
                qmax.pollLast();
            }
            qmax.addLast(i);

            if (qmax.peekFirst() == i - w) {
                qmax.pollFirst();
            }

            if (i - w + 1 >= 0) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
        int[] res = getMaxWindow(arr, 3);
        for (int item : res) {
            System.out.print(item + " ");
        }
    }
}