LeetCode 239. 滑动窗口最大值
目录
题目描述
题意分析
一个长度为
k的窗口从数组最左端起，每次向右挪一格，直到右端贴住数组末尾；要求依次报出每个位置上窗口内的最大值。窗口的右端点从k - 1走到n - 1，所以答案的长度恰好是n - k + 1。数据规模给出了最强的信号：数组长度可达 $10^5$，而
k可以接近n，逐窗口重新扫描的量级是 $O(nk)$，在最坏情况下会到 $10^{10}$ 级别，必须被排除。也就是说，相邻窗口之间必须复用信息，不能各算各的。第二个信号来自窗口的移动方式：每挪一格只发生两件事——最左边一个元素离开、最右边一个元素加入。这说明变化量是常数，而不是整层重算；同时也说明所需的数据结构要在两端都能改动，一端接纳新来的，另一端淘汰过时的。
还有一点容易被忽略：题目求的是最大值本身，并不要求知道它在窗口里的位置，因此凡是「不可能再成为任何后续窗口最大值」的元素都可以被永久丢掉，不必保留完整窗口内容。这一点是把复杂度压下来的入口。
需要留意的边界情形：
k = 1时每个窗口就是元素自身，答案等于原数组；k = n时只有一个窗口；数组允许出现负数，因此不能用0或任何正数当作「最大值」的初值；数组也允许出现重复值，处理相等元素时要有明确的取舍规则。
解法：单调队列维护候选下标
核心思路
用单调队列保存仍可能成为最大值的下标：下标从队头到队尾递增，对应值递减。队头始终是当前窗口最大值；新元素加入前，先删除过期下标，再从队尾删除不大于新元素的候选。
解题步骤
- 遍历数组，下标
i作为窗口右端点。- 删除队头中满足
index <= i - k的过期下标。- 删除队尾所有满足
nums[index] <= nums[i]的下标，再将i入队。- 当窗口形成后，将队头对应的值加入结果。
代码实现
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.pollFirst();
}
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
}
func maxSlidingWindow(nums []int, k int) []int {
result := make([]int, 0, len(nums)-k+1)
deque := make([]int, 0, k)
for i := range nums {
for len(deque) > 0 && deque[0] <= i-k {
deque = deque[1:]
}
for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
deque = deque[:len(deque)-1]
}
deque = append(deque, i)
if i >= k-1 {
result = append(result, nums[deque[0]])
}
}
return result
}
复杂度分析
- 时间复杂度：$O(n)$，每个下标最多入队、出队各一次。
- 空间复杂度：$O(k)$，队列最多保存一个窗口的下标。
关键点总结
- 队列存下标，才能同时判断元素是否过期并取得对应值。
- 队列按值单调递减，因此队头就是窗口最大值。
- 弹出相等的旧值，保留更晚过期的新下标。
易错点总结
- 过期条件漏掉等号，会把刚滑出窗口的元素继续当作候选。
- 队尾只弹一次，无法恢复单调性，必须使用循环。
- 先入队再清理队尾，会把当前下标与自身比较并删除。
- 输出的是
nums[deque[0]]，不是队头下标。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 862. 和至少为 K 的最短子数组 | 困难 | 单调队列作用在前缀和上且维护递增，窗口长度不固定，队头淘汰依据从位置换成条件已满足 |
| 1438. 绝对差不超过限制的最长连续子数组 | 中等 | 要同时维护最大值和最小值两个队列，窗口长度可变，由极差是否超限驱动左边界收缩 |
| 剑指 Offer 59 - I. 滑动窗口的最大值 | 困难 | 与本题同题换号，但要额外处理空数组输入，不能直接按 n - k + 1 分配结果 |
| 剑指 Offer 59 - II. 队列的最大值 | 中等 | 改成在线设计题，没有固定窗口，出队时要判断被删元素是否恰好是当前最大值 |
| 907. 子数组的最小值之和 | 中等 | 用单调栈而非队列，关注的是每个元素作为最小值的支配区间长度，需要贡献法计数 |