单调队列 - 数据结构

什么是单调队列？

单调队列是一种特殊的双端队列（Deque），其内部元素具有严格的单调递增或单调递减性。它常用于在 $O(N)$ 时间复杂度内解决如下问题：

经典问题：滑动窗口最大值 (Sliding Window Maximum)

给定一个长度为 $N$ 的数组 $A$ 和一个大小为 $k$ 的滑动窗口。窗口从数组最左侧滑到最右侧，每次向右移动一位。输出窗口在每个位置时的最大值。

普通暴力算法：每个窗口内扫描最值，时间复杂度为 $O(N \times k)$。
单调队列算法：每个元素最多入队一次、出队一次，均摊时间复杂度为极其高效的 $O(N)$。

单调队列核心维护原则（以滑动窗口最大值为例）

排除过期元素 (Out of bounds)：当窗口向右滑动时，队列头部的索引如果小于当前窗口的左边界，说明该元素已滑出窗口范围，从队头（Front）弹出。
维护单调性 (Monotonicity Squeeze)：当一个新元素准备从队尾入队时，为了保持队列自头向尾递减（队头最大），我们会将它与队尾元素比较。如果队尾元素小于新元素，由于队尾元素既小又出现得早，未来绝无可能成为最大值，因此从队尾（Back）依次弹出，直到队尾元素大于新元素或队列为空。
新元素入队与输出：将新元素索引压入队尾。当处理完前 $k-1$ 个元素后，每个时刻的队头元素即为当前窗口的最大值。

数组大小：窗口大小 $k$：

点击"下一步"或"自动演示"开始学习单调队列

原数组 A

双端队列 Q (维护元素索引，自头向尾递减)

◀ 队头 (Front)

队尾 (Back) ▶

窗口最大值结果 Res

C++ 核心代码对照

滑动窗口最大值 C++ 实现

vector<int> maxSlidingWindow(vector<int>& arr, int k) {
    vector<int> res;
    deque<int> q; // 双端队列，存储数组索引

    for (int i = 0; i < arr.size(); i++) {
        // 1. 弹出已滑出窗口范围的队头元素
        if (!q.empty() && q.front() <= i - k) {
            q.pop_front();
        }

        // 2. 弹出队尾所有小于当前值的元素，维护队列的单调性
        while (!q.empty() && arr[q.back()] < arr[i]) {
            q.pop_back();
        }

        // 3. 将当前元素的索引压入队尾
        q.push_back(i);

        // 4. 当窗口形成后，记录当前窗口的最大值（即队头对应的元素）
        if (i >= k - 1) {
            res.push_back(arr[q.front()]);
        }
    }
    return res;
}

实际应用与扩展

滑动窗口最小值：只需将单调队列的维护原则改为“压入新元素前弹出队尾大于新元素的元素”，保持队列自头向尾单调递增，队头即为最小值。
单调队列优化 DP：在一些区间动态规划问题中，如状态转移方程为 $dp[i] = \min_{i-k \le j < i} \{ dp[j] + calc(j) \}$ 时，利用单调队列维护前 $k$ 个决策点的最值，可以将 $O(N \times k)$ 的 DP 复杂度降为极佳的 $O(N)$。
多重背包单调队列优化：利用剩余系划分状态，把多重背包转化为多个滑动窗口最值问题进行完美优化。