LeetCode239 窗口最大值

题目

传送门

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

这是一个 hard 级别的题目，难点在于如何维护窗口中的元素。

第一想法

题目要求滑动窗口每一个状态下的最大元素。最自然的暴力解法是，窗口每滑动一次，就遍历里面的所有值，求出最大值，时间复杂度为 O(n*k)。

为了提高效率，很多同学（比如我）会想到优先队列。优先队列确实可以自动维护最值，但窗口滑动时，我们就无法弹出多余的元素了。因此没有任何一个现成的数据结构可以解决这个问题。

解析

从优先队列的缺点入手，可以得出另一个极端情况：只保存当前的最大值，每滑动一格就把新元素与最大值比对。这算法显然不行， 我们不能忽略其他元素，因为窗口滑动之后，最大的元素有可能在它们之中，而不是新加入的那个。

但，真的所有元素都值得作为候选元素吗？

例如：

[1 3 2] -3 5 6 7; k=3

对于当前的窗口，我们需要保留 3,2，但无需保留第一个元素 1。因为：

• 1 不是当前的最大值，并且
• 1 在窗口滑动时会被淘汰。

事实上，3 （当前窗口内的最大元素）之前的所有元素都没必要保留。因为：

• 若 3 在窗口内，则最大值至少是 3，不可能是前面的元素。
• 若 3 已经弹出，则它之前的元素肯定早已弹出。

至此，可以得出第一个结论：我们只需从最大的元素开始记录。 为了实现这个效果，可以设计一个队列，每当添加新元素，从队尾开始，弹出所有比它小的元素，然后再入队，

为什么不从队头开始弹出？

假设这样一个情况：[1 6 2] 5 4; k=3，此时队列应该为 6,2。 窗口开始滑动，若从队头开始弹出，则新的队列为 6,2,5。继续滑动弹出 6，队列为 2,5,4。显然，这不是从最大的元素出开始记录的。

当窗口滑动需要淘汰元素时，也不用真的弹出。只有要淘汰的元素正好是队头元素时，才需要执行弹出操作，因为之前的元素我们根本没有记录（相当于提前弹出）。

按照这个操作，可以得出第二个结论：我们队列一定是非递增的，第一个元素永远是最大的，并且所有元素都在当前窗口里。

代码 (java)

代码有一个更好理解的写法：自定义一个队列类，在其入队、出队的操作中添加上述判断。

但是这么写略麻烦，我们可以把这些判断直接加到主体代码中，语义没那么清晰，但代码量少一些：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> q = new LinkedList<>(); // 双向队列，允许弹出队尾元素
        for (int i = 0; i < nums.length; i++) {
            // insert
            while (!q.isEmpty() && q.getLast() < nums[i])
                q.removeLast(); // 从队尾开始弹出所有较小的元素
            q.add(nums[i]);

            if (i >= k) {
                // pop 已达窗口大小，需要淘汰元素
                if (nums[i - k] == q.peek())
                    q.poll();
            }
            // calc result
            if (i >= k - 1) {
                result[i - k + 1] = q.peek(); // 队头始终是最大的元素
            }
        }
        return result;
    }
}