c++中如何使用队列实现滑动窗口最大值_c++队列实现滑动窗口最大值-C++-PHP中文网

c++中如何使用队列实现滑动窗口最大值_c++队列实现滑动窗口最大值

下次还敢

发布： 2025-09-26 17:13:01

原创

952人浏览过

使用双端队列维护滑动窗口最大值，核心是保持队列递减。遍历数组，移除队首过期索引，从队尾删除小于等于当前值的索引，确保队首始终为当前窗口最大值。当i≥k-1时，将队首对应值加入结果。时间复杂度O(n)，空间复杂度O(k)。

c++中如何使用队列实现滑动窗口最大值_c++队列实现滑动窗口最大值

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

给定一个数组 nums 和滑动窗口大小 k，从左到右每次滑动一格，输出每个窗口中的最大值。

示例：
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
输出：[3, 3, 5, 5, 6, 7]

我们维护一个递减的双端队列 deque，存储的是数组元素的索引，而非值本身。队列前端始终保存当前窗口最大值的索引。

关键规则：

#include <vector>
#include <deque>
using namespace std;

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);

        // 窗口大小达到k后，记录最大值
        if (i >= k - 1)
            result.push_back(nums[dq.front()]);     }

return result;
}

时间复杂度：O(n)，每个元素最多入队和出队一次。
空间复杂度：O(k)，双端队列中最多保存k个元素。

Tanka

具备AI长期记忆的下一代团队协作沟通工具

110

注意点：

基本上就这些，掌握单调队列的思想后，类似问题也能轻松应对。

以上就是c++++中如何使用队列实现滑动窗口最大值_c++队列实现滑动窗口最大值的详细内容，更多请关注php中文网其它相关文章！

大家都在看：