LeetCode239 窗口最大值
题目
You are given an array of integers
nums
, there is a sliding window of sizek
which is moving from the very left of the array to the very right. You can only see thek
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;
}
}