滑动窗口最大值
Sliding Window Maximum
给定数组和窗口大小 k，窗口从左向右滑动，返回每个窗口中的最大值。
在力扣中练习题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1 输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
解题思路
主解法
单调队列 · 存下标
队首永远是当前窗口最大值，队尾维护递减
每个窗口都重新找最大值是 O(nk)。观察窗口滑动时只有两个变化：右边进一个数，左边可能出一个数。
用一个双端队列存下标：
- 新元素入队前，从队尾弹掉所有不大于它的元素——它们不可能再成为最大值；
- 下标超出窗口左边界时，从队首弹出；
- 队首就是当前窗口最大值。
自拟主例 [4,2,7,3,5,1]，k=3：7 到来时把 4、2 都从队尾挤掉；最后一个 1 入队后，7 的下标过期，队首变成 5。
分步图解
i = 0，nums[0] = 4；入队。
- i
- 0
- deque
- 0
每个下标最多入队一次、出队一次，时间 O(n)，空间 O(k)。
分步图解
i = 3，nums[3] = 3；入队。窗口最大值 7。
- i
- 3
- deque
- 2,3
时间 O(n)空间 O(k)
易错点
- 队列存值而不是下标：无法判断队首是否已经滑出窗口。
- 先取结果再清理过期队首：可能把已经离开窗口的最大值写进答案。
- 用 < 而不是 <= 弹队尾：相等元素会残留在队列里，窗口变长后可能误判。
- 只在 i == k-1 时取结果：之后每个窗口都要记录。
对照解法
大顶堆 · 延迟删除
堆顶是最大值，过期就弹掉
时间 O(n log n)，比单调队列慢；但实现简单，适合面试先写出可运行版本，再优化到 O(n)。
把窗口内的元素放进大顶堆，堆顶就是最大值。窗口右移时，旧元素不会立刻删除，而是等到它浮到堆顶、且下标已经过期时再弹出。
每个元素入堆一次、出堆至多一次，时间 O(n log n)，空间 O(n)。它不如单调队列快，但“延迟删除”的思路很通用，适合处理滑动窗口 + 最值。
- 1i 从 0 到 n-1：把 (nums[i], i) 入堆。
- 2窗口形成后，若堆顶下标 <= i-k，弹出。
- 3记录堆顶的值。
时间 O(n log n)空间 O(n)
易错点
- 堆里只存值：无法判断堆顶是否过期。
- 窗口还没形成就开始记录：i < k-1 时堆里元素不足 k 个。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
nums = [4,2,7,3,5,1], k = 3deque 存下标，值从队首到队尾递减；先处理前几个元素。
- k
- 3
查看 C++ 代码
延伸阅读
- 单调队列适合“窗口内的最值”；如果要求窗口内第 k 大，需要换成两个堆或有序结构。
- 队列里存下标而不是值，是所有滑动窗口过期判断的共同要求。