滑动窗口最大值
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
速度
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值。
示例 1
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
模拟答题者思考
1. 暴力法：对每个窗口遍历找最大值，O(nk)。问题：k 接近 n 时太慢。
2. 重复劳动在哪？相邻窗口共享 k-1 个元素，只有一个出队一个入队。每次重新扫太浪费。
3. 我需要一个能快速获取最大值、支持滑动更新的结构 → 单调队列：维护候选最大值的递减序列。
4. 单调队列的妙处：新元素入队时，比它小的「旧元素」永远不可能成为答案，直接弹出。队首一定最大。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dq | deque<int> | 定义：候选最大值下标队列（值单调递减） 维护：队首始终是当前窗口的最大值下标 更新：入队时弹出所有 ≤ nums[i] 的旧元素；窗口右移时若队首滑出窗口则弹出 |
i - k + 1 | int | 定义：当前窗口的左边界下标 维护：随 i 递增 更新：每轮右移窗口时 +1 |
落码步骤
1. 初始化双端队列 dq（存下标）
2. 遍历 nums，先弹出窗口外元素：while dq[0] <= i - k: dq.popleft()
3. 维护单调递减：while dq and nums[dq[-1]] <= nums[i]: dq.pop()
4. dq.append(i)（新下标入队）
5. 当 i >= k-1（窗口形成），ans.append(nums[dq[0]])
代码实现
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
dq = deque() # 存下标，值单调递减
ans = []
for i in range(len(nums)):
# 1. 弹出滑出窗口的下标
if dq and dq[0] <= i - k:
dq.popleft()
# 2. 维护单调递减：弹出所有 ≤ nums[i] 的旧元素
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
# 3. 新下标入队
dq.append(i)
# 4. 窗口形成后，队首就是当前窗口最大值
if i >= k - 1:
ans.append(nums[dq[0]])
return ansclass Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
deque dq; // 存下标，值单调递减
vector ans;
for (int i = 0; i < nums.size(); i++) {
// 1. 弹出滑出窗口的下标
if (!dq.empty() && dq.front() <= i - k)
dq.pop_front();
// 2. 维护单调递减：弹出所有 <= nums[i] 的旧元素
while (!dq.empty() && nums[dq.back()] <= nums[i])
dq.pop_back();
// 3. 新下标入队
dq.push_back(i);
// 4. 窗口形成后，队首就是当前窗口最大值
if (i >= k - 1)
ans.push_back(nums[dq.front()]);
}
return ans;
}
};
// 时间 O(n)，空间 O(k) 复杂度分析
时间复杂度
O(n)
空间复杂度
O(k)
常见坑
弹出顺序：必须先弹出窗口外元素（dq[0] <= i-k），再维护单调性。
维护单调性要用 <= 而非 <：遇到相等值也要弹出旧元素，保证队首是「最近」的最大值（虽然不影响本题结果，但更规范）。
忘记窗口还没形成时不能记录答案：只有当 i >= k-1 时才把队首加入结果。
必测边界 Case
Case 1：k=1
nums = [1,-1,2], k = 1 → 输出 [1,-1,2]（每个窗口就是单个元素）
Case 2：k=n
nums = [3,1,2], k = 3 → 输出 [3]
Case 3：单调递减数组
nums = [5,4,3,2,1], k = 3 → 输出 [5,4,3]