C++怎么实现滑动窗口最大值_C++单调队列优化【算法】

直接用 std::priority_queue 会超时，因其无法删除窗口外旧元素，堆顶可能过期，需反复检查下标导致最坏 o(nk)；稳定 o(n) 解法应使用单调递减下标队列。

为什么直接用 std::priority_queue 会超时

滑动窗口最大值最直观的想法是每移一次窗口就调用 std::max_element，但 O(nk) 复杂度在 k 接近 n 时直接 TLE；换成 std::priority_queue 看似能降成 O(n log k)，问题在于它无法按需删除窗口外的旧元素——堆顶可能是早已滑出的值，导致结果错误或重复判断。

实操建议：

立即学习“C++免费学习笔记（深入）”；

• 每次取堆顶后必须检查其下标是否仍在当前窗口内（即 idx >= i - k + 1），否则 pop 并重试
• 这意味着实际单次操作可能连续 pop 多次，最坏仍是 O(nk)
• 真正稳定 O(n) 的解法依赖单调队列，不是堆

用 deque 维护单调递减下标队列

核心不是存值，而是存数组下标，并保证对应值严格递减。这样队首永远是当前窗口最大值的下标，且可快速剔除过期和更小的候选。

实操建议：

立即学习“C++免费学习笔记（深入）”；

• 遍历 i 从 0 到 n-1，对每个 i：
  • 弹出队尾所有对应值 ≤ nums[i] 的下标（维持递减）
  • 把 i 压入队尾
  • 弹出队首所有 的下标（剔除过期）
  • 当 i >= k - 1 时，nums[deque.front()] 就是答案
• 注意：必须用下标而非值入队，否则无法判断过期
• 不要在循环里反复调用 deque.size() 判断是否为空，先 !deque.empty() 再取 front()

手写循环数组模拟双端队列更省空间？

用 vector 或原生数组模拟单调队列确实能避免 deque 的内存分配开销，但在现代 STL 实现中，std::deque 的常数已很优；手动模拟只在极端嵌入式场景或题目强制禁用 STL 时才必要。

实操建议：

立即学习“C++免费学习笔记（深入）”；

• 若真要手写，用两个指针 head 和 tail 管理环形缓冲区，容量设为 k + 1 即可（窗口最多存 k 个有效下标）
• 弹出队尾 = --tail；压入队尾 = buf[tail++] = i；弹出队首 = ++head
• 关键陷阱：判断队空要用 head == tail，队满是 (tail + 1) % cap == head，别错写成 tail - head == cap

LeetCode 239 题常见边界错误

提交失败往往不是算法错，而是没处理好窗口大小为 1、数组为空、k > n 这几类输入。

实操建议：

立即学习“C++免费学习笔记（深入）”；

• k == 1 时直接返回原数组，避免冗余逻辑引入越界
• k > n 是合法输入，此时整个数组就是一个窗口，答案只有一个值：*max_element(nums.begin(), nums.end())
• 初始化阶段不要提前把前 k-1 个元素全塞进队列再开始主循环，而应统一在主循环中处理每个 i，靠 i >= k - 1 控制输出时机
• 错误信息如 heap-buffer-overflow 很可能源于访问了 nums[deque.front()] 前没检查 deque 是否为空

单调队列的“单调”二字容易让人误以为要维护值的单调性，其实维护的是下标对应值的单调性，且必须是递减——这点一旦理解偏差，后续所有逻辑都会跑偏。