在C++中如何使用滑动窗口算法高效求解数组指定区间内的最大值？

在C++中，使用**单调双端队列（deque）**是实现滑动窗口求区间最大值的高效方法，可将时间复杂度从暴力的O(n*k)降至O(n)，其中n为数组长度，k为窗口大小。

核心步骤

1. 初始化一个std::deque<int>用于存储数组元素的索引。
2. 遍历数组，对于每个索引i：
   • 检查队首索引是否已滑出当前窗口（即队首索引 <= i - k），若是则弹出队首。
   • 从队尾开始，若当前元素大于等于队尾索引对应的元素，则不断弹出队尾，以维持队列的单调递减性。
   • 将当前索引i压入队尾。
3. 当遍历到 i >= k - 1 时，队首索引对应的元素即为当前窗口的最大值。

C++代码示例

#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 < nums.size(); ++i) {
        if (!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) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

判断依据

• 单调性：队列中索引对应的元素值严格单调递减，保证队首始终是窗口内的最大元素。
• 有效性：通过比较队首索引与窗口左边界，确保队列中只包含当前窗口内的元素。

适用条件

• 数组元素固定且需要连续多次查询等长区间的极值。
• 对时间复杂度要求较高的大规模数据处理场景。

常见误区

• 存值而非索引：如果队列中直接存储元素值而非索引，将无法准确判断队首元素是否已经滑出窗口边界。
• 弹出条件错误：维护单调性时应使用 <= 而非 <，否则当窗口内存在重复最大值时，旧的最大值索引可能未被及时清理，导致过期索引残留在队列中。
• 忽略窗口未形成阶段：在 i < k - 1 时不应输出结果，此时窗口尚未填满。