一.单调队列简介
1.1单调队列定义与特性本质：
单调队列是一种特殊的队列结构，其内部元素始终保持单调递增或单调递减的顺序。
核心规则：当新元素入队列时，会通过弹出破坏单调性的队首元素来维持有序性。
单调方向：
单调递增栈：从队列首到队列尾，元素逐渐变大（例如 [1,3,5,7][1,3,5,7]）。
单调递减栈：从队列首到队列尾，元素逐渐变小（例如 [9,6,2,1][9,6,2,1]）。
1.2应用场景
1. 滑动窗口最大值/最小值
单调队列最典型的应用是动态维护滑动窗口内的极值。例如，给定数组和窗口大小 kk，要求实时输出窗口滑动时的最大值或最小值。
2. 子数组最小值之和
题目要求计算所有连续子数组的最小值之和（如引用[1]的问题）。虽然通常用单调栈解决，但单调队列可优化特定条件下的动态范围操作。
3. 动态规划优化
在动态规划问题中，若状态转移方程涉及某区间内的极值，可用单调队列减少时间复杂度。
二.模板代码
2.1代码
for (int i = 0; i < n; i++) {// 维护单调性：移除比当前元素大的队尾元素while (!q.empty() && a[i] <= a[q.back()]) {q.pop_back();}q.push_back(i);// 移除超出窗口范围的队首元素while (q.front() <= i - k) {q.pop_front();}// 当窗口形成后记录结果if (i >= k - 1) {res.push_back(a[q.front()]);}
}2.2实现解析
- 双端队列选择：使用
deque容器支持O(1)时间的头尾操作 - 单调性维护：通过
while循环确保队列元素单调递增（nums[i]<=nums[q.back()]nums[i]<=nums[q.back()]），若需要最大值队列则改为>=比较 - 窗口范围检查：
q.front() <= i - k判断队首是否超出当前窗口左边界 - 时间复杂度：每个元素最多入队出队各一次，整体O(n)时间复杂度
三.例题《切蛋糕》
#include<bits/stdc++.h>
using namespace std;deque<int> q; // 单调队列，存储可能的左端点索引j，保持sum[j-1]递增
int n, k, a[500005], sum[500005], maxx = -0x3f3f3f3f; // sum为前缀和数组，maxx记录最大值int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出cin >> n >> k; // 输入n和k（k对应题目中的m）for(int i = 1; i <= n; i++){cin >> a[i];sum[i] = sum[i-1] + a[i]; // 计算前缀和}for(int i = 1; i <= n; i++){// 维护队列的单调性：保证队列中的sum[j-1]递增// 当当前sum[i-1]比队尾的sum[j-1]更小，队尾的元素不可能成为最优解，弹出while(!q.empty() && sum[q.back()-1] > sum[i-1]){q.pop_back();}q.push_back(i); // 将当前索引i加入队列，作为可能的左端点// 维护窗口大小：确保子数组长度不超过k// 若当前i与队首的距离超过k，弹出队首if(i - q.front() + 1 > k){q.pop_front();}// 计算以i为右端点的最大子段和，并更新最大值maxx = max(maxx, sum[i] - sum[q.front()-1]);}cout << maxx;return 0;
}