暴力遍历时间复杂度O(n×k)近O(n²)，不适用于大数据流；单调队列用deque存下标维护递减序列，保证O(n)时间与O(k)空间，核心是下标存储以支持过期判断和递减性维护。
滑动窗口最大值为什么不能用暴力遍历
每次窗口移动都重新找一遍最大值，时间复杂度是 O(n * k)，当 k 接近 n 时接近 O(n²)。实际中比如处理百万级传感器数据流，这种写法会明显卡顿甚至超时。
真正实用的解法依赖单调队列——不是 STL 的 std::queue，而是用 std::deque 维护一个递减序列，保证队首始终是当前窗口最大值的下标。
用 std::deque 实现单调队列的关键操作
核心不是存值，是存数组下标，这样才能判断元素是否已滑出窗口；同时要维持队列内对应值严格递减。
- 每轮循环前，检查
deque.front()是否小于等于i - k（即已过期），是则pop_front() - 从队尾开始，只要
nums[deque.back()] <= nums[i]，就pop_back()—— 保证递减性 - 把当前下标
ipush_back() - 当
i >= k - 1（即窗口已形成），取nums[deque.front()]作为结果
示例片段：
立即学习“C++免费学习笔记（深入）”；
std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
std::deque<int> dq;
std::vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) res.push_back(nums[dq.front()]);
}
return res;
}
deque 和 vector 做单调队列的区别
必须用 std::deque，不能用 std::vector 模拟：因为需要在两端高效增删，vector::pop_front() 是 O(n)，会把整体拉回 O(n²)。
另外注意几个边界易错点：
-
k == 0或nums为空时，直接返回空vector -
k == 1时，结果就是原数组，但代码逻辑仍适用，无需特判 - 输入
k > nums.size()属于非法输入，按题意通常不需处理，但生产环境建议加断言
如果必须用 priority_queue 怎么办
可以，但得配合延迟删除：用大顶堆存 {value, index}，每次取堆顶时检查 index 是否仍在窗口内。问题在于过期元素不会自动清除，堆可能堆积大量无效项，最坏空间 O(n)，且常数较大。
相比单调队列的 O(n) 时间 + O(k) 空间，priority_queue 版本实际性能差一截，只适合快速验证逻辑或面试兜底。
真正要注意的是：单调队列里维护的是下标而非数值，这个设计选择直接影响了窗口过期判断和去重逻辑——漏掉这点，整个结构就失去意义。
