不能直接用std::priority_queue，因其仅支持堆顶删除，无法按滑动顺序剔除过期元素，需懒删除导致最坏O(n log n)；而单调队列用std::deque维护下标，通过队尾弹出≤当前值、队首检查过期，确保O(n)且队首恒为窗口最大值。
为什么不能直接用 std::priority_queue？
因为堆无法按窗口滑动顺序删除过期元素——std::priority_queue 只能 pop 顶部最大值，但窗口左边界收缩时，该最大值可能早已不在当前窗口内。你得手动“懒删除”，但这样会破坏 O(1) 均摊复杂度，最坏退化到 O(n log n)。
真正需要的是一个支持「前端删除（出队）+ 后端增删（维护单调性）」的结构，即双端队列（std::deque），用来实现单调递减队列。
单调队列怎么保证队首永远是当前窗口最大值？
核心是入队时从队尾开始弹出所有 小于等于 当前元素的值——这样队列始终严格单调递减，且保留了更大、更“长寿”的候选者。同时，每次滑动前检查队首索引是否已移出窗口（q.front() ），是则弹出。
- 队列里存的是
nums的下标，不是值，方便判断是否过期 - 比较用
nums[q.back()] ，等号必须包含：相同值时留后出现的，它存活时间更长 - 窗口大小为
k，有效窗口范围是[i - k + 1, i]，所以队首索引就该删
C++ 实现要点与易错细节
注意边界：第一个完整窗口出现在 i == k - 1 时，此前不记录答案；另外，deque 判空必须用 q.empty()，不能只靠 q.front() 访问。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q; // 存下标
vector<int> res;
for (int i = 0; i = k - 1)
res.push_back(nums[q.front()]);
}
return res;
}</int></int></int></int>
- 不要写成
nums[q.back()] （漏掉等号）：遇到重复最大值如[3,3,3,3]，队列只剩最后一个下标，前面窗口就取不到正确最大值 - 不要在
push_back(i)之后立即检查并pop_front()：顺序反了，可能把刚进来的i错误弹出（当k==1时尤其明显） -
if (i >= k - 1)是安全下限，比if (q.size() == k)可靠得多——队列长度 ≠ 窗口长度
和 std::multiset 对比有什么实际影响？
用 multiset 能模拟滑动窗口：插入、删除指定值、取 rbegin()，代码看似简洁，但每次操作都是 O(log k)，总时间 O(n log k)，且内存开销大；而单调队列是严格 O(n)，每个下标最多入队出队各一次。实测在 n=1e6、k=1e4 场景下，单调队列快 3–5 倍，且无动态内存分配抖动。
真正难的不是写对逻辑，而是理解为什么「删队尾小数 + 查队首是否过期」这两个动作就能覆盖所有窗口状态——它本质是用空间换确定性：放弃保存所有历史信息，只维护对后续决策有用的“支配性候选”。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
