栈与队列 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

[图片上传失败...(image-cda983-1710751580816)]

思路

这个题最大的问题是怎么找出滑动窗口中的最大值，也就是怎么利用结构低成本的找饿到最大值。这里我们实现一个单调队列（单调队列缓存数据，当缓存的元素大于前面元素将小的元素全部移除，直到前面的元素大于当前缓存的元素。

滑动最大窗口.gif

/**
 * 239. 滑动窗口最大值 单调队列
 */

public class MaxSlidingWindow239 {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        if (length == 1) {
            return nums;
        }

        //前k个元素产生一个最大值，
        //K后每移动一个产生一个最大值
        int[] res = new int[1 + length - k];

        // result数组下标
        int index = 0;
        MyQueue myQueue = new MyQueue();
        for (int i = 0; i < k; i++) {
            myQueue.push(nums[i]);
        }
        // 缓存第一个K 内的最大值
        res[index++] = myQueue.getMax();

        for (int i = k; i < length; i++) {
            // 将非本窗口元素删除
            myQueue.poll(nums[i - k]);
            // 将新的元素添加进去
            myQueue.push(nums[i]);
            res[index++] = myQueue.getMax();
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        // 输出：[3,3,5,5,6,7]
        int[] result = maxSlidingWindow(nums, k);
        for (int i : result) {
            System.out.print(i + "   ");
        }
    }
}

class MyQueue {
    Deque<Integer> deque = new LinkedList<>();

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

    public void push(int val) {
        // 新增元素的时候会将所有小于这个元素的元素全部弹出
        while (!deque.isEmpty() && deque.peekLast() < val) {
            deque.removeLast();
        }
        deque.add(val);
    }

    public int getMax() {
        return deque.peek();
    }
}

image.png