数据结构——单调队列

一.单调队列简介

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实现解析

1. 双端队列选择：使用deque容器支持O(1)时间的头尾操作
2. 单调性维护：通过while循环确保队列元素单调递增（nums[i]<=nums[q.back()]nums[i]<=nums[q.back()]），若需要最大值队列则改为>=比较
3. 窗口范围检查：q.front() <= i - k判断队首是否超出当前窗口左边界
4. 时间复杂度：每个元素最多入队出队各一次，整体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;
}

加纳！！！！！