单调队列
单调队列是一种特殊的双端队列，队列中的元素保持单调性（递增或递减）。它常用于解决滑动窗口问题，能够在O(1)时间内获取窗口内的最值，总体时间复杂度为O(n)。单调队列是动态规划优化和区间查询问题的重要工具。
单调队列基础
单调队列维护队列中元素的单调性，通过双端队列实现，支持队首队尾的插入和删除操作。
单调队列基础实现 - 滑动窗口最大值
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
class MonotonicQueue {
private:
deque<int> dq; // 存储数组索引
vector<int> arr;
public:
MonotonicQueue(vector<int>& array) : arr(array) {}
// 维护单调递减队列（队首元素最大）
void push(int index) {
// 移除队尾所有小于等于当前元素的索引
while (!dq.empty() && arr[dq.back()] <= arr[index]) {
dq.pop_back();
}
dq.push_back(index);
}
// 如果队首元素已经不在窗口内，则移除
void pop(int index) {
if (!dq.empty() && dq.front() == index) {
dq.pop_front();
}
}
// 获取队列中的最大值
int getMax() {
return dq.empty() ? -1 : arr[dq.front()];
}
// 获取队列中的最小值（需要维护单调递增队列）
int getMin() {
return dq.empty() ? -1 : arr[dq.back()];
}
bool empty() {
return dq.empty();
}
};
// 滑动窗口最大值问题
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> dq;
for (int i = 0; i < nums.size(); i++) {
// 移除超出窗口的元素
while (!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;
}
// 滑动窗口最小值问题
vector<int> minSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> dq;
for (int i = 0; i < nums.size(); i++) {
// 移除超出窗口的元素
while (!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;
}
// 双端单调队列 - 同时维护最大值和最小值
class DualMonotonicQueue {
private:
deque<int> maxDq; // 单调递减队列
deque<int> minDq; // 单调递增队列
vector<int> arr;
public:
DualMonotonicQueue(vector<int>& array) : arr(array) {}
void push(int index) {
// 维护最大值队列
while (!maxDq.empty() && arr[maxDq.back()] <= arr[index]) {
maxDq.pop_back();
}
maxDq.push_back(index);
// 维护最小值队列
while (!minDq.empty() && arr[minDq.back()] >= arr[index]) {
minDq.pop_back();
}
minDq.push_back(index);
}
void pop(int index) {
if (!maxDq.empty() && maxDq.front() == index) {
maxDq.pop_front();
}
if (!minDq.empty() && minDq.front() == index) {
minDq.pop_front();
}
}
int getMax() {
return maxDq.empty() ? -1 : arr[maxDq.front()];
}
int getMin() {
return minDq.empty() ? -1 : arr[minDq.front()];
}
int getRange() {
if (maxDq.empty() || minDq.empty()) return 0;
return arr[maxDq.front()] - arr[minDq.front()];
}
};
int main() {
vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
cout << "原数组: ";
for (int x : nums) cout << x << " ";
cout << "\n窗口大小: " << k << endl;
// 测试滑动窗口最大值
vector<int> maxResult = maxSlidingWindow(nums, k);
cout << "\n滑动窗口最大值: ";
for (int x : maxResult) cout << x << " ";
cout << endl;
// 测试滑动窗口最小值
vector<int> minResult = minSlidingWindow(nums, k);
cout << "滑动窗口最小值: ";
for (int x : minResult) cout << x << " ";
cout << endl;
// 测试双端单调队列
cout << "\n双端单调队列测试:\n";
DualMonotonicQueue dmq(nums);
cout << "窗口\t最大值\t最小值\t极差" << endl;
for (int i = 0; i < nums.size(); i++) {
dmq.push(i);
// 移除超出窗口的元素
if (i >= k) {
dmq.pop(i - k);
}
if (i >= k - 1) {
cout << "[" << (i - k + 1) << "," << i << "]\t"
<< dmq.getMax() << "\t" << dmq.getMin() << "\t" << dmq.getRange() << endl;
}
}
return 0;
}单调队列通过维护队列中元素的单调性来快速获取区间最值。队列存储数组索引而非值，方便处理窗口边界。双端单调队列同时维护最大值和最小值队列。
单调队列优化动态规划
单调队列常用于优化动态规划中的状态转移，将O(nk)的复杂度优化到O(n)。
单调队列优化DP - 最大子序列和
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
// 长度限制的最大子数组和
class ConstrainedSubsequenceSum {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> dp(n);
deque<int> dq; // 按dp值递减顺序存储索引
for (int i = 0; i < n; i++) {
// 移除约束范围外的索引
while (!dq.empty() && dq.front() < i - k) {
dq.pop_front();
}
// dp[i] = nums[i] + max(0, max(dp[j] for j in [i-k, i-1]))
dp[i] = nums[i];
if (!dq.empty()) {
dp[i] = max(dp[i], nums[i] + dp[dq.front()]);
}
// 维护递减顺序，只保留正的dp值
while (!dq.empty() && dp[dq.back()] <= dp[i]) {
dq.pop_back();
}
if (dp[i] > 0) {
dq.push_back(i);
}
}
return *max_element(dp.begin(), dp.end());
}
};
// 和至少为K的最短子数组
class ShortestSubarrayWithSumK {
public:
int shortestSubarray(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> prefixSum(n + 1, 0);
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
deque<int> dq; // 维护前缀和的递增顺序
int minLen = INT_MAX;
for (int i = 0; i <= n; i++) {
// 检查当前前缀和是否可以形成有效子数组
while (!dq.empty() && prefixSum[i] - prefixSum[dq.front()] >= k) {
minLen = min(minLen, i - dq.front());
dq.pop_front();
}
// 维护前缀和的递增顺序
while (!dq.empty() && prefixSum[dq.back()] >= prefixSum[i]) {
dq.pop_back();
}
dq.push_back(i);
}
return minLen == INT_MAX ? -1 : minLen;
}
};
// 跳跃游戏优化
class JumpGameOptimization {
public:
int jump(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return 0;
vector<int> dp(n, INT_MAX);
dp[0] = 0;
deque<int> dq;
dq.push_back(0);
for (int i = 1; i < n; i++) {
// 移除无法到达当前位置的位置
while (!dq.empty() && dq.front() + nums[dq.front()] < i) {
dq.pop_front();
}
if (!dq.empty()) {
dp[i] = dp[dq.front()] + 1;
}
// 按dp值顺序维护位置
while (!dq.empty() && dp[dq.back()] >= dp[i]) {
dq.pop_back();
}
dq.push_back(i);
}
return dp[n - 1];
}
};
// 使用单调队列的直方图最大矩形
class LargestRectangleHistogram {
public:
int largestRectangleArea(vector<int>& heights) {
deque<int> dq; // 维护递增高度
int maxArea = 0;
for (int i = 0; i <= heights.size(); i++) {
int currentHeight = (i == heights.size()) ? 0 : heights[i];
while (!dq.empty() && heights[dq.back()] > currentHeight) {
int height = heights[dq.back()];
dq.pop_back();
int width = dq.empty() ? i : i - dq.front() - 1;
maxArea = max(maxArea, height * width);
}
dq.push_back(i);
}
return maxArea;
}
};
int main() {
// 测试约束子序列和
cout << "约束子序列和:\n";
vector<int> nums1 = {10, 2, -10, 5, 20};
int k1 = 2;
ConstrainedSubsequenceSum css;
cout << "数组: ";
for (int x : nums1) cout << x << " ";
cout << "\n最大距离: " << k1 << endl;
cout << "最大和: " << css.constrainedSubsetSum(nums1, k1) << endl;
// 测试和为K的最短子数组
cout << "\n和至少为K的最短子数组:\n";
vector<int> nums2 = {2, -1, 2};
int k2 = 3;
ShortestSubarrayWithSumK ssk;
cout << "数组: ";
for (int x : nums2) cout << x << " ";
cout << "\n目标和: " << k2 << endl;
cout << "最短长度: " << ssk.shortestSubarray(nums2, k2) << endl;
// 测试跳跃游戏优化
cout << "\n跳跃游戏优化:\n";
vector<int> nums3 = {2, 3, 1, 1, 4};
JumpGameOptimization jgo;
cout << "数组: ";
for (int x : nums3) cout << x << " ";
cout << "\n最少跳跃次数: " << jgo.jump(nums3) << endl;
// 测试直方图最大矩形
cout << "\n直方图最大矩形:\n";
vector<int> heights = {2, 1, 5, 6, 2, 3};
LargestRectangleHistogram lrh;
cout << "高度: ";
for (int x : heights) cout << x << " ";
cout << "\n最大面积: " << lrh.largestRectangleArea(heights) << endl;
return 0;
}单调队列优化DP的核心是维护决策点的单调性，避免重复计算。在背包问题中按余数分组处理，在子数组问题中维护前缀和的单调性。
单调队列的高级应用
单调队列在复杂问题中的应用，包括多维优化、在线算法等。
单调队列的高级应用 - 在线算法和多维优化
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <algorithm>
using namespace std;
// 在线维护滑动窗口的中位数
class SlidingWindowMedian {
private:
multiset<int> small, large; // small存储较小的一半，large存储较大的一半
int k;
void balance() {
if (small.size() > large.size() + 1) {
large.insert(*small.rbegin());
small.erase(small.find(*small.rbegin()));
} else if (large.size() > small.size() + 1) {
small.insert(*large.begin());
large.erase(large.begin());
}
}
double getMedian() {
if (k % 2 == 1) {
return small.size() > large.size() ? *small.rbegin() : *large.begin();
} else {
return (*small.rbegin() + *large.begin()) / 2.0;
}
}
public:
SlidingWindowMedian(int windowSize) : k(windowSize) {}
vector<double> medianSlidingWindow(vector<int>& nums) {
vector<double> result;
for (int i = 0; i < nums.size(); i++) {
// 添加新元素
if (small.empty() || nums[i] <= *small.rbegin()) {
small.insert(nums[i]);
} else {
large.insert(nums[i]);
}
// 移除超出窗口的元素
if (i >= k) {
int toRemove = nums[i - k];
if (small.find(toRemove) != small.end()) {
small.erase(small.find(toRemove));
} else {
large.erase(large.find(toRemove));
}
}
balance();
if (i >= k - 1) {
result.push_back(getMedian());
}
}
return result;
}
};
// 二维滑动窗口最大值
class Matrix2DSlidingWindow {
public:
vector<vector<int>> maxSlidingWindow2D(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> result(m - k + 1, vector<int>(n - k + 1));
// 对每一行应用一维滑动窗口最大值
vector<vector<int>> rowMax(m, vector<int>(n - k + 1));
for (int i = 0; i < m; i++) {
deque<int> dq;
for (int j = 0; j < n; j++) {
while (!dq.empty() && dq.front() <= j - k) {
dq.pop_front();
}
while (!dq.empty() && matrix[i][dq.back()] <= matrix[i][j]) {
dq.pop_back();
}
dq.push_back(j);
if (j >= k - 1) {
rowMax[i][j - k + 1] = matrix[i][dq.front()];
}
}
}
// 对每一列应用一维滑动窗口最大值
for (int j = 0; j < n - k + 1; j++) {
deque<int> dq;
for (int i = 0; i < m; i++) {
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
while (!dq.empty() && rowMax[dq.back()][j] <= rowMax[i][j]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1) {
result[i - k + 1][j] = rowMax[dq.front()][j];
}
}
}
return result;
}
};
// 约束条件下的最优决策
class ConstrainedDecision {
public:
int maxScore(vector<int>& nums, int maxJump) {
int n = nums.size();
vector<int> dp(n, INT_MIN);
dp[0] = nums[0];
deque<int> dq;
dq.push_back(0);
for (int i = 1; i < n; i++) {
// 移除超出范围的决策点
while (!dq.empty() && dq.front() < i - maxJump) {
dq.pop_front();
}
// 转移状态
if (!dq.empty()) {
dp[i] = dp[dq.front()] + nums[i];
}
// 维护单调性
while (!dq.empty() && dp[dq.back()] <= dp[i]) {
dq.pop_back();
}
dq.push_back(i);
}
return dp[n - 1];
}
};
int main() {
// 测试滑动窗口中位数
cout << "滑动窗口中位数:\n";
vector<int> nums1 = {1, 3, -1, -3, 5, 3, 6, 7};
SlidingWindowMedian swm(3);
vector<double> medians = swm.medianSlidingWindow(nums1);
cout << "数组: ";
for (int x : nums1) cout << x << " ";
cout << "\n窗口大小3的中位数: ";
for (double x : medians) cout << x << " ";
cout << endl;
// 测试二维滑动窗口
cout << "\n二维滑动窗口最大值:\n";
vector<vector<int>> matrix = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
Matrix2DSlidingWindow m2d;
vector<vector<int>> result2d = m2d.maxSlidingWindow2D(matrix, 2);
cout << "原矩阵:\n";
for (auto& row : matrix) {
for (int x : row) cout << x << "\t";
cout << endl;
}
cout << "2x2窗口最大值:\n";
for (auto& row : result2d) {
for (int x : row) cout << x << "\t";
cout << endl;
}
// 测试约束条件下的最优决策
cout << "\n约束条件下的最大得分:\n";
vector<int> scores = {1, -1, -2, 4, -7, 3};
ConstrainedDecision cd;
cout << "分数数组: ";
for (int x : scores) cout << x << " ";
cout << "\n最大步长为2的最大得分: " << cd.maxScore(scores, 2) << endl;
return 0;
}高级应用展示了单调队列在多维问题、在线算法中的威力。滑动窗口中位数使用双set维护，二维滑动窗口分别对行列应用单调队列，约束决策问题通过维护可达状态的单调性优化。
竞赛技巧总结
单调队列的核心思想：
- 维护队列中元素的单调性（递增或递减）
- 通过双端队列支持队首队尾的高效操作
- 每个元素最多进出队列一次，保证O(n)复杂度
- 适用于滑动窗口和动态规划优化问题
常见应用场景：
- 滑动窗口最值问题：维护窗口内的最大值或最小值
- 动态规划优化：优化状态转移的时间复杂度
- 背包问题变形：多重背包的单调队列优化
- 子数组问题：最大子数组和的各种变形
- 决策优化：在约束条件下的最优决策
实现技巧：
- 存储索引而非值：便于处理窗口边界和元素位置
- 及时清理过期元素：保持队列的有效性
- 正确维护单调性：根据问题需求选择递增或递减
- 边界处理：注意窗口形成的时机和条件
调试要点：
- 检查单调性的维护逻辑
- 确认窗口边界的处理
- 验证队列清理的时机
- 测试边界情况（空队列、单元素等）
复杂度分析：
- 时间复杂度：每个元素最多进出队列一次，总体O(n)
- 空间复杂度：O(k)，其中k是窗口大小或状态数
- 相比朴素算法的O(nk)复杂度有显著提升
扩展应用：
- 多维滑动窗口：分别对每个维度应用单调队列
- 在线算法：结合其他数据结构处理动态查询
- 并行优化：利用单调队列的性质进行并行处理
- 近似算法：在近似算法中维护候选解集合