题目leetcode239
一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。滑动窗口每次只向右移动一位，最终返回滑动窗口中的最大值 。
示例

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

解题思路

思路1：采用最大堆，堆的元素数量为 k，时间复杂度 logk * n
思路2：
采用双端队列，前后都可以弹出元素，每个元素只在队列里存在一次，时间复杂度 O(n)；
先把窗口的前 k - 1 填满；
窗口开始向前滑动，往窗口新增一个数填满窗口，选出最大值，判断队首元素是否有效，无效则移除。

image.png

IMG_1774.jpg

class Solution {
    private static class MyDeque{
        private Deque<Integer> deque = new LinkedList();
        public MyDeque() {}

        // 在队尾添加元素，并把前面比新元素小的元素删除掉，从队尾开始删，最大的元素最终在队首
        public void push(int n) {
            while (!deque.isEmpty() && deque.getLast() < n) {
                deque.pollLast();
            }
            deque.addLast(n);
        }

        public int max() {
            // 返回队首元素，不删除
            return deque.peekFirst();
        }

        public void pop(int n) {
            // 如果队首元素下标 = i-k+1，即deque.peekFirst() == nums[i-k+1,i]则为无效元素，需要移除
            if (!deque.isEmpty() && deque.peekFirst() == n) {
                deque.pollFirst();
            }
        }
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        MyDeque window = new MyDeque();
        // 存放每次的最大值
        int[] result = new int[nums.length - k + 1];
        int num = 0;
        // 前 k-1 个直接 push
        for (int i = 0; i < k - 1; i++) {
            window.push(nums[i]);
        }
        // 窗口向前滑动
        for (int i = k - 1; i < nums.length; i++) {
            // 队尾增加一个元素
            window.push(nums[i]);
            // 找出最大值，即队首
            result[num++] = window.max();
            // 判断队首元素是否无效，无效则移除
            window.pop(nums[i - k + 1]);
        }
        return result;
    }
}