滑动窗口最大值不能用普通队列，因其无法o(1)获取最大值，遍历导致o(nk)复杂度；单调队列通过维护严格递减双端队列，保证队首为当前窗口最大值。
滑动窗口最大值为什么不能用普通队列
因为普通队列（比如 collections.deque 仅做 FIFO）无法在 O(1) 时间内获取当前窗口内的最大值。每次窗口滑动后，你得遍历整个窗口找最大值，时间复杂度退化为 O(nk)，k 是窗口大小。单调队列的核心是维护一个「从队首到队尾严格递减」的双端队列，保证队首永远是当前窗口最大值。
如何用 deque 实现单调递减队列
关键不是“存什么”，而是“删什么”：新元素入队前，把队尾所有 ≤ 它的数都弹出，确保队列单调递减；同时检查队首是否已滑出窗口，及时移除。
- 入队操作：
while dq and nums[dq[-1]] → 清掉队尾更小或相等的值 - 出队时机：
if dq[0] == i - k: dq.popleft()→ 队首索引等于左边界外侧时淘汰 - 答案取值：
nums[dq[0]]→ 队首索引对应值即为当前窗口最大值 - 注意：队列里存的是数组下标，不是数值本身 —— 这样才能准确判断是否越界、方便取值
完整可运行代码与边界处理要点
下面是最简健壮实现，已覆盖空输入、k=1、k==len(nums) 等边界：
from collections import deque
<p>def maxSlidingWindow(nums, k):
if not nums or k == 0:
return []
dq = deque()
res = []
for i in range(len(nums)):</p><h1>移除队首越界元素（i-k 是上一窗口左边界，当前左边界是 i-k+1）</h1><pre class="brush:python;toolbar:false;"> if dq and dq[0] == i - k:
dq.popleft()
# 维护单调递减：弹出所有 ≤ 当前值的队尾元素
while dq and nums[dq[-1]] = k-1）
if i >= k - 1:
res.append(nums[dq[0]])
return res
常见错误包括：dq[0] == i - k 写成 或漏判；<code>i >= k - 1 判断位置放错导致结果多一位；用数值代替索引入队导致无法判断越界。
为什么不用堆或线段树
堆（如 heapq）虽能动态求最大值，但无法高效删除指定元素（窗口左边界滑出时需删旧值），惰性删除会累积无效节点，最坏仍是 O(n log n)。线段树/ST 表适合离线查询，不支持窗口实时滑动更新。单调队列是唯一能把均摊时间压到 O(n) 的方案 —— 每个元素最多入队、出队各一次。
真正容易被忽略的是：单调队列不是“维护最大值”，而是“维护可能成为未来最大值的候选者”。那些被弹出的小值，不是因为它们错了，是因为它们已经被更大的、更晚出现的数“永久遮蔽”了。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
