c++中如何实现滑动窗口最大值_c++滑动窗口最大值实现方法

穿越時空

发布： 2025-10-13 21:56:01

原创

563人浏览过

使用双端队列可在O(n)时间解决滑动窗口最大值问题：遍历数组，维护存储下标的deque，确保队首为当前窗口最大值下标，通过弹出过期和较小值元素保持单调性，窗口形成后记录结果。

c++中如何实现滑动窗口最大值_c++滑动窗口最大值实现方法

在C++中实现滑动窗口最大值，最高效的方法是使用双端队列（deque）来维护窗口内可能成为最大值的元素索引。这种方法可以在O(n)时间复杂度内解决该问题，避免对每个窗口都进行重复遍历。

使用双端队列实现滑动窗口最大值

核心思想是：用一个deque保存当前窗口中元素的下标，且保证队首始终是当前窗口最大值的下标。为了维持这一性质，需要按以下规则操作：

遍历数组时，如果队列非空且队首元素已滑出窗口范围（即下标小于 i - k + 1），将其从队首弹出
在将当前元素下标加入队列前，从队尾开始删除所有对应值小于等于当前元素值的下标，因为这些元素不可能再成为后续窗口的最大值
将当前下标加入队尾
当遍历到第k个元素及之后时，队首就是当前窗口最大值，记录结果

// 示例代码

include <vector>

include <deque>

using namespace std;

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

vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; vector<int> result;

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;

登录后复制

}