239. 滑动窗口最大值（Sliding Window Maximum）
频次 ★★★★★ · 难度 🔴 · 高频：字节/阿里/美团
题目
长度 k 的窗口从左到右滑过数组，输出每个位置的窗口最大值。
示例：
输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]
思路
单调递减双端队列（存下标）：
- 队头永远是当前窗口最大值的下标
- 新元素入队前，从队尾弹掉所有比它小的——它们在新元素在场期间永无出头之日
- 队头下标滑出窗口范围（
<= i - k）时从队头弹出
每个下标进出队各一次，O(n)。
代码
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> dq = new ArrayDeque<>(); // 存下标,对应值单调递减
int n = nums.length;
int[] res = new int[n - k + 1];
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i])
dq.pollLast(); // 弹掉"更小且更旧"的
dq.offerLast(i);
if (dq.peekFirst() <= i - k) dq.pollFirst(); // 队头滑出窗口
if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
}
return res;
}复杂度
- 时间：O(n) —— 每个元素至多进队/出队一次
- 空间：O(k) —— 队列长度不超过窗口
边界条件
- k = 1：输出原数组
- k = n：只输出全局最大值
- 全递减数组：队列长度达到 k，队头持续输出
变式
- 滑动窗口最小值：队列改单调递增
- 队列存值而非下标：无法判断队头是否过期，必须存下标——面试常见的追问点
- 求窗口最大值之和/差：同款队列，只改输出
易错点
- 弹队尾的条件
<=（相等也弹）：留新不留旧，旧的先过期 - 判断过期用下标（
dq.peekFirst() <= i - k），不能用值——窗口里可能有重复值 - 出结果的时机是
i >= k - 1，结果下标i - k + 1 - 用
LinkedList也能当 Deque，但ArrayDeque无结点分配开销更快，见集合框架
面试追问
- 为什么不用大顶堆？ 堆能做但 O(n log n)：过期元素懒删除，堆顶出窗时才弹。单调队列把”过期”和”被压制”两类无用元素都及时清掉才到 O(n)——能对比两种方案取舍再给结论
- 单调队列和单调栈什么关系？ 都维护单调性淘汰”不可能成为答案”的候选；栈只关心一端（最近的更大/更小），队列因为窗口会过期需要两端操作