c++中如何实现单调队列_c++单调队列实现方法-C++-PHP中文网

c++中如何实现单调队列_c++单调队列实现方法

穿越時空

发布： 2025-10-13 20:00:01

原创

978人浏览过

单调队列是双端队列，维护元素下标对应的值单调递减或递增，用于滑动窗口最值问题。1. 用std::deque存储下标，便于判断是否过期；2. 插入前从队尾删除小于当前值的下标，保持单调性；3. 队首超出窗口时移除；4. 从第k个元素开始记录结果。时间复杂度O(n)，优于暴力法。

c++中如何实现单调队列_c++单调队列实现方法

在C++中，单调队列通常用于解决滑动窗口类问题，比如求滑动窗口最大值、最小值，或满足某种单调性要求的子数组问题。单调队列的核心思想是维护一个队列，使得其中的元素在值上保持单调递增或递减，同时保证下标顺序。

什么是单调队列

单调队列是一种双端队列（deque），它从队首到队尾的元素值保持单调性（递增或递减）。常见的是单调递减队列用于求最大值，单调递增队列用于求最小值。关键在于：每当我们加入一个新元素时，从队尾开始删除所有“不再有希望成为答案”的元素。

使用std::deque实现单调队列

我们可以借助C++标准库中的std::deque来高效实现单调队列。以下是一个求滑动窗口最大值的典型例子：

示例：滑动窗口最大值

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

给定一个数组 nums 和窗口大小 k，输出每个窗口内的最大值。

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

查看详情

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

        // 窗口形成后，队首就是当前窗口最大值的下标
        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }

    return result;
}

登录后复制