单调队列与滑动窗口最值CSP-S

💡 核心思想

单调队列是一种双端队列，队列中的元素保持单调递增或递减。最典型的应用是"滑动窗口最值"：给定一个数组和一个固定大小的窗口，求窗口滑动过程中每个位置的最大值（或最小值）。通过维护单调性，可以在 O(n) 时间内完成，而不是暴力 O(n·k)。

🎯 直觉理解

想象你在看一场演出，窗户只能看到连续的 5 个人。你想知道每次窗户滑动时，最高的人是谁。单调队列就像一个"候选名单"：新人如果比名单里所有人都高，前面矮的人就永远不可能成为最高了，直接踢出名单。窗户滑走时，如果最高的人刚好离开视野，就把他从名单头部移除。

📝 算法流程

1. 初始化一个双端队列 deque（存下标，保持值单调递减）
2. 遍历数组的每个元素：
3. 移除队头超出窗口范围的元素
4. 从队尾移除所有值 <= 当前元素的元素（它们不可能成为最大值）
5. 当前元素入队尾
6. 队头就是当前窗口的最大值
7. 每个元素最多入队出队一次，总复杂度 O(n)

$$\text{滑动窗口最大值：} max_{i in [L,R]} a_i \text{，窗口每次滑动 1 位} Rightarrow O(n)\text{ 用单调队列}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 单调队列：滑动窗口最大值
vector maxSlidingWindow(vector& a, int k) {
    vector res;
    deque dq; // 存下标，保持 a[dq.front()] 单调递减
    
    for (int i = 0; i < a.size(); i++) {
        // 1. 移除窗口外的元素
        if (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        
        // 2. 从队尾移除所有 <= 当前元素的（不可能成为最大值）
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        
        // 3. 当前元素入队
        dq.push_back(i);
        
        // 4. 记录窗口最大值（从第 k-1 个元素开始）
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

// 单调队列优化多重背包
// dp[i] = max{dp[i - j*w] + j*v} for j in [0, cnt]
// 按模 w 分组，每组用单调队列优化

int main() {
    vector a = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    auto res = maxSlidingWindow(a, k);
    for (int x : res) cout << x << " "; // 3 3 5 5 6 7
    cout << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目