单调队列是双端队列，维护元素下标对应的值单调递减或递增，用于滑动窗口最值问题。1. 用std::deque存储下标，便于判断是否过期；2. 插入前从队尾删除小于当前值的下标，保持单调性；3. 队首超出窗口时移除；4. 从第k个元素开始记录结果。时间复杂度O(n)，优于暴力法。
在C++中，单调队列通常用于解决滑动窗口类问题，比如求滑动窗口最大值、最小值，或满足某种单调性要求的子数组问题。单调队列的核心思想是维护一个队列，使得其中的元素在值上保持单调递增或递减，同时保证下标顺序。
什么是单调队列
单调队列是一种双端队列（deque），它从队首到队尾的元素值保持单调性（递增或递减）。常见的是单调递减队列用于求最大值，单调递增队列用于求最小值。关键在于：每当我们加入一个新元素时，从队尾开始删除所有“不再有希望成为答案”的元素。
使用std::deque实现单调队列
我们可以借助C++标准库中的std::deque来高效实现单调队列。以下是一个求滑动窗口最大值的典型例子：
示例：滑动窗口最大值
立即学习“C++免费学习笔记（深入）”；
给定一个数组 nums 和窗口大小 k，输出每个窗口内的最大值。
#include #include using namespace std;vector maxSlidingWindow(vector& nums, int k) { deque dq; // 存储数组下标，保证对应值单调递减 vector 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()] = k - 1) result.push_back(nums[dq.front()]); } return result;}
关键操作说明
上述代码的关键点如下：
存储下标而非值：便于判断元素是否还在窗口内。维护单调性：每次插入前，从队尾删除所有对应值小于当前值的下标，确保队列单调递减。处理过期元素：当队首下标超出窗口左边界时，将其弹出。结果收集时机：从第k个元素开始（即 i >= k-1），每个位置都可以输出一个窗口最大值。
扩展：单调递增队列（求最小值）
如果要维护单调递增队列以获取窗口最小值，只需修改比较条件：
“`cppwhile (!dq.empty() && nums[dq.back()] > nums[i]) dq.pop_back();“`
其余逻辑保持一致。
基本上就这些。掌握单调队列的关键是理解“用空间换优势”——通过维护一个结构，把O(nk)暴力优化到O(n)。核心是双端队列的操作和单调性的维护。不复杂但容易忽略细节。
以上就是c++++中如何实现单调队列_c++单调队列实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1478843.html
微信扫一扫 
支付宝扫一扫 
