11.滑动窗口最大值

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：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

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

题解思路

单调递减队列

这道题需要使用一种叫做单调递减队列的数据结构，这个队列的队列头始终是队列最大值，然后从头到尾数值依次变小，向该队列中添加元素时需要进行特殊处理，比如向队列中添加num，需要判断队列尾部的值是否大于num，如果小于，此时直接入队则会破坏队列单调递减的特性，则需要将队尾元素出队，然后继续判断，直到找到队列中比num值大的数或者队列为null，然后将num入队

图解单调递减队列

使用单调递减队列，在滑动窗口时，将窗口内的值加入单调递减队列，如果单调队列的最大值「头节点」被移出滑动窗口，则移出头元素，代码如下i >= k && nums[i - k] == queue.peek()，其中nums[ i - k ]就是刚刚移出窗口的值，如果这个值大于了队列中的最大值，则说明这个最大值已经出了滑动窗口范围，需要从队列中移除queue.poll()；

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3，动画如下：

当i >= k - 1时，每次将队列中的最大值加入结果集合，why？因为一开始指针i是从0开始的，此时窗口还没有真正展开，此时队列中的最大值也不作数，因为你不确定后面窗口内会不会还有更大的值。简单来说，就是需要等窗口真正打开时，窗口内的最大值才能算数，比如现在 k ==3，即窗口大小为3，那么需要指针 i 指向 2 时窗口大小才真正成为3，此时才需要记录第一个最大值。

题解代码

/**
 *  单调递减队列，移出元素的逻辑中队列外实现
 */
static class MonotonicStack {
    // 双端队列
    private final LinkedList<Integer> deque = new LinkedList<>();

    // 查看递减队列的第一个元素
    public Integer peek() {
        return deque.peekFirst();
    }

    // 查看并移除递减队列的第一个元素
    public void poll() {
        deque.pollFirst();
    }

    // 向递减队列中添加元素
    public void offer(Integer m) {
        // 队尾元素如果小于待添加元素，则出队
        while (!deque.isEmpty() && deque.peekLast() < m) {
            deque.pollLast();
        }
        deque.offerLast(m);
    }

}

public int[] maxSlidingWindow(int[] nums, int k) {
    // 单调递减队列
    MonotonicStack queue = new MonotonicStack();
    // 结果集合
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        queue.offer(num);
        // 滑动窗口最前面的一个元素就是nums[ i - k ]
        // 如果滑动窗口前面的第一个元素等于了队列中的最大值，说明这个最大值已经出了滑动窗口范围
        if (i >= k && nums[i - k] == queue.peek()) {
            queue.poll();
        }
        // 从i >= k-1 开始，每次将队列中的最大值加入结果集合
        if (i >= k - 1) {
            list.add(queue.peek());
        }
    }
    return list.stream()
            .mapToInt(Integer::intValue)
            .toArray();
}

// 移出元素的逻辑在队列中实现
static class Solution {
    static class MyQueue {
        Deque<Integer> deque = new LinkedList<>();

        //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
        void poll(int val) {
            if (!deque.isEmpty() && val == deque.peek()) {
                deque.poll();
            }
        }

        // 添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出，保证队列元素单调递减
        // 比如此时队列元素3,1，此时2将要入队，比1大，所以1弹出，此时队列：3,2
        void add(int val) {
            while (!deque.isEmpty() && val > deque.getLast()) {
                deque.removeLast();
            }
            deque.add(val);
        }

        //队列队顶元素始终为最大值
        int peek() {
            return deque.peek();
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        //存放结果元素的数组
        int[] res = new int[nums.length - k + 1];
        int resIdx = 0;
        //自定义队列
        MyQueue myQueue = new MyQueue();
        //先将前k的元素放入队列
        for (int i = 0; i < k; i++) {
            myQueue.add(nums[i]);
        }
        res[resIdx++] = myQueue.peek();
        for (int i = k; i < nums.length; i++) {
            //滑动窗口移除最前面的元素
            myQueue.poll(nums[i - k]);
            //滑动窗口加入最后面的元素
            myQueue.add(nums[i]);
            //记录对应的最大值
            res[resIdx++] = myQueue.peek();
        }
        return res;
    }
}