题源分类/程序员代码面试指南：IT名企算法与数据结构题目最优解/java/栈和队列/getMaxWindow.java
import java.util.LinkedList;

import org.junit.Test;

// # 生成窗口最大值数组
// # 【题目】
// # 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，
// # 窗口每次向右边滑一个位置。例如，数组为[4，3，5，4，3，3，6，7]，
// # 窗口大小为3时：[插图]如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。
// # 请实现一个函数。
// # ● 输入：整型数组arr，窗口大小为w。
// # ● 输出：一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。
// # 以本题为例，结果应该返回{5，5，5，4，6，7}。【难度】尉 ★★☆☆

public class getMaxWindow {

    @Test
    public void test() {

        int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 };
        int w = 3;

        int[] res = getMW(arr, w);
        for (int i : res) {
            System.out.print(i);

        }
    }

    public int[] getMW(int[] arr, int w) {

        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }

        LinkedList<Integer> qmax = new LinkedList<>();
        int index = 0;
        int[] res = new int[arr.length - w + 1];

        for (int i = 0; i < arr.length; 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) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }

        return res;
    }

}
