LeetCode 239困难单调队列
滑动窗口最大值 图解题解
每个 k 大小的窗口里最大值是多少？一个单调递减队列扫一遍全搞定。
像一列火车车厢只留「有用候选」：每滑进一节新车厢，就把队尾那些比它矮的旧车厢全踢掉（它们既比新的小、又比新的旧，永远不可能当答案）；同时检查队头车厢是否已滑出窗口、超出就弹掉。最终队头就是当前窗口最大值。队列里的元素始终从大到小排列，每个元素最多进出一次。
这道题到底在问什么
给数组和窗口大小 k，返回每个窗口里的最大值。
- nums
- [1,3,-1,-3,5,3,6,7], k=3
- 输出
- [3,3,5,5,6,7]
最优解：一步一步想明白
⚠️ 容易写错的地方
✗ 错：每个窗口都重新 max
✓ 对：用单调队列维护候选最大值
重新扫描会 O(nk)
✗ 错：只按样例推代码
✓ 对：先写清状态含义和边界条件
样例太少，隐藏用例专打边界
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
from collections import deque
class Solution:
def maxSlidingWindow(self, nums, k):
q = deque()
ans = []
for i, x in enumerate(nums):
while q and q[0] <= i - k:
q.popleft()
while q and nums[q[-1]] <= x:
q.pop()
q.append(i)
if i >= k - 1:
ans.append(nums[q[0]])
return ansC++
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q; vector<int> ans;
for (int i = 0; i < (int)nums.size(); i++) {
while (!q.empty() && q.front() <= i - k) q.pop_front();
while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
q.push_back(i);
if (i >= k - 1) ans.push_back(nums[q.front()]);
}
return ans;
}
};Java
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> q = new ArrayDeque<>();
int[] ans = new int[nums.length - k + 1];
int idx = 0;
for (int i = 0; i < nums.length; i++) {
while (!q.isEmpty() && q.peekFirst() <= i - k) q.pollFirst();
while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) q.pollLast();
q.offerLast(i);
if (i >= k - 1) ans[idx++] = nums[q.peekFirst()];
}
return ans;
}
}套路模板 · 单调队列
# 单调队列 通用检查表
# 1. 定义状态/指针/容器
# 2. 每轮只做一个清晰动作
# 3. 更新答案并处理边界class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q; vector<int> ans;
for (int i = 0; i < (int)nums.size(); i++) {
while (!q.empty() && q.front() <= i - k) q.pop_front();
while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
q.push_back(i);
if (i >= k - 1) ans.push_back(nums[q.front()]);
}
return ans;
}
};class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> q = new ArrayDeque<>();
int[] ans = new int[nums.length - k + 1];
int idx = 0;
for (int i = 0; i < nums.length; i++) {
while (!q.isEmpty() && q.peekFirst() <= i - k) q.pollFirst();
while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) q.pollLast();
q.offerLast(i);
if (i >= k - 1) ans[idx++] = nums[q.peekFirst()];
}
return ans;
}
}复杂度
时间复杂度
O(n)
每个核心状态按算法要求处理固定次数
空间复杂度
O(k)
只保存必要的辅助结构或递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 滑动窗口最大值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么单调队列是 O(n)？+
每个元素最多入队、出队各一次，总共 O(n)；比每个窗口求最大(O(nk))快得多。
队列为什么单调递减？+
新元素若比队尾大，队尾那些更早更小的永远不可能再当最大，直接弹掉。
和用堆比？+
堆 O(n log k) 且要处理过期元素；单调队列 O(n) 更优，是本题标准解。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。