文章

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;
    }
}