数据结构和算法【6】窗口最大值数组

public class CodingDemo {

    public static int[] getMaxWindowArr(int[] arr, int w){
        if (arr == null || arr.length < w || w < 1){
            return null;
        }

        //1,创建双端队列
        LinkedList<Integer> queue = new LinkedList<Integer>();

        //2，创建结果数组, 长度等于 arr.length-w+1，
        //因为生成了 arr.length-w+1 个窗口
        int[] res = new int[arr.length - w + 1];
        int index = 0;

        //3，开始遍历数组
        for (int i = 0; i < arr.length; i++) {

            //3.1 如果队尾对应值小于当前遍历值，则弹出队尾，直到队尾对应数组值大于当前值
            while (!queue.isEmpty() && arr[queue.peekLast()] <= arr[i]){
                queue.pollLast();
            }

            //3.2 加入当前 i
            queue.addLast(i);

            if (queue.peekFirst() == i-w){
                queue.pollFirst();//窗口过期了，需要移除队头
            }

            //3.3 因为i从0开始，除了需要等待第一个窗口生成，
            //后面每移动一步，都会有窗口，不需要等待
            if (i+1 >= w){
                res[index++] = arr[queue.peekFirst()];//记录此窗口最大值
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {4,3,5,4,3,3,6,7};
        System.out.println(Arrays.toString(getMaxWindowArr(arr, 3)));
    }
}

D:\java\bin\java.exe
[5, 5, 5, 4, 6, 7]