C++ 第48题：单调双端队列应用：滑动窗口最大值高效求解

题目

编写程序，解决高难度经典算法“滑动窗口最大值”（Sliding Window Maximum）。给定一个整数数组与滑动窗口大小 k，窗口从最左向最右滑动，返回每个窗口位置中的最大值。利用 std::deque 构建单调双端队列，在 O(N) 线性时间与 O(k) 额外空间内完成计算，分析为什么传统大顶堆 O(N log k) 无法做到这一极致效率。

输入格式：无需外部输入。

输出格式：输出滑动窗口每次滑动时的最大值序列。

数据范围与约定：数组长度 <code>N ≤ 10^5</code>，单调队列双端弹出。

思路与算法

1. 为什么 priority_queue 不够完美
大顶堆可以在 O(1) 取最大值，但当窗口滑出左边界元素时，大顶堆无法在 O(1) 内删除特定位置的元素，只能依赖延迟删除，堆大小可能膨胀至 O(N)，单步调整耗时 O(log N)。

2. 单调双端队列的核心约束
std::deque 中存储元素在数组中的下标。队列维护两个单调契约：①下标单调递增；②对应数值严格单调递减。因此队列头部 dq.front() 永远是当前窗口内最大的元素下标。

3. 两头清理策略
队尾清理：新元素入队前，把队尾所有对应数值 <= 新元素的下标全部从尾部 pop_back；队头清理：若 dq.front() <= i - k，说明队头最大值已经滑出窗口范围，从头部 pop_front。

完整程序

#include <iostream>
#include <vector>
#include <deque>

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
    std::vector<int> result;
    std::deque<int> dq; // 存储数组索引，保持队列内对应元素单调递减

    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        // 1. 弹出滑出窗口左边界的过期索引
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 2. 淘汰队尾所有小于当前值的索引，维持单调性
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }

        // 3. 当前索引入队
        dq.push_back(i);

        // 4. 当窗口形成（i >= k - 1）时，队头即为窗口最大值
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

int main() {
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    std::cout << "测试数组: {1, 3, -1, -3, 5, 3, 6, 7}, 窗口大小 k = " << k << "\n";
    std::vector<int> maxVals = maxSlidingWindow(nums, k);

    std::cout << "各滑动窗口最大值结果序列: ";
    for (int val : maxVals) {
        std::cout << val << " ";
    }
    std::cout << "\n";

    return 0;
}

运行示例

输出：

测试数组: {1, 3, -1, -3, 5, 3, 6, 7}, 窗口大小 k = 3
各滑动窗口最大值结果序列: 3 3 5 5 6 7