题目描述

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

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

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

题目分析

优先队列

使用优先队列存储窗口内的数字，就可以依靠优先队列的排序特性获取最大值。实际代码中，存储的是下标（通过下标也可以直接获取到对应值，相当于存储了两个信息），通过自定义规则来实现对数字的从大到小排序。
每次移动窗口时，把新数字添加到窗口内。最左侧退出窗口的数字理论上需要删除，但优先队列中查找元素的时间复杂度为 O(n)，因此删除一个指定的元素，效率并不高。可以先不删除，在读取最大值时，如果下标不在滑动窗口范围内，再把它删除（此时是队首删除，复杂度 logn）。
数组长度为 n ，队列内最多会存储 n 个元素，总时间复杂度为 O(n * log n)。

单调队列

题目中要求的是最大值，对于窗口内的数字，如果比最新加入窗口的数字还小，则已经可以删掉了。
因此我们可以手动维护一个列表，存储数字的下标，每次从尾部添加数据。在添加前检查旧的尾部下标对应的数字是否应该被移除（如果移除则继续检查尾部，直到尾部对应数据 > 即将添加的下标对应数据）。最终效果就是，列表从头到尾下标递增，且下标对应的数字递减。
每次移动窗口都是在上一次的基础上对单调队列做维护，因此效率很高。
每个下标都只会被添加一次、删除一次，整体时间复杂度为 O(n).

Java

// 优先队列
public int[] maxSlidingWindow1(int[] nums, int k) {
    PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return Integer.compare(nums[o2], nums[o1]);
        }
    });
    int r = 0;
    int[] ans = new int[nums.length - k + 1];
    for (int l = 0; l <= nums.length - k; l++) {
        while (r < l + k) {
            queue.offer(r);
            r++;
        }

        while (queue.peek() < l) {
            queue.poll();
        }
        ans[l] = nums[queue.peek()];
    }
    return ans;
}

// 单调队列
public int[] maxSlidingWindow2(int[] nums, int k) {
    LinkedList<Integer> list = new LinkedList<>();
    int[] ans = new int[nums.length - k + 1];
    for (int l = 0, r = 0; l <= nums.length - k; l++) {
        while (r < l + k) {
            Integer last = list.peekLast();
            if (last != null && nums[last] < nums[r]) {
                list.pollLast();
            } else {
                list.offerLast(r++);
            }
        }
        while (list.peekFirst() < l) {
            list.pollFirst();
        }

        ans[l] = nums[list.peekFirst()];
    }

    return ans;
}

Kotlin

// 优先队列
fun maxSlidingWindow1(nums: IntArray, k: Int): IntArray {
    val ans = IntArray(nums.size - k + 1)
    val queue = PriorityQueue<Int>(object : Comparator<Int> {
        override fun compare(o1: Int, o2: Int): Int {
            return nums[o2].compareTo(nums[o1])
        }
    })
    var r = 0
    for (l in 0..nums.size - k) {
        while (r < l + k) {
            queue.offer(r++)
        }
        while (queue.peek() < l) {
            queue.poll()
        }
        ans[l] = nums[queue.peek()]
    }
    return ans
}

// 单调队列
fun maxSlidingWindow2(nums: IntArray, k: Int): IntArray {
    val ans = IntArray(nums.size - k + 1)
    val list = LinkedList<Int>()
    var r = 0
    for (l in 0..nums.size - k) {
        while (r < l + k) {
            val last = list.peekLast()
            if (last != null && nums[last] < nums[r]) {
                list.pollLast()
            } else {
                list.offerLast(r++)
            }
        }
        while (list.peekFirst() < l) {
            list.pollFirst()
        }
        ans[l] = nums[list.peekFirst()]
    }

    return ans
}