单调队列优化动态规划：从“逐个比较”到“高效排队”

动态规划做状态转移时，常常需要从前面一段连续的状态中挑出一个最优值（比如最大值）。如果每次从头到尾扫一遍，时间复杂度就会很高。单调队列优化就是给DP装上一个“滑动窗口加速器”——用一个特殊的队列维护窗口内的候选值，把每次找最值的时间从O(k)降到O(1)，让整个算法能从O(nk)变成O(n)。

什么是单调队列？

单调队列是一个队列，但它内部元素的值（或对应的dp值）始终保持单调递增或递减。我们用双端队列（deque）来实现，因为需要从队尾移除元素，也要从队首弹出过期的元素。

核心思想：如果一个新来的元素比队尾的“更大”（求最大值时），那么队尾那个元素就永远没机会成为窗口里的最大值了，因为新元素更新、更大，而且存活时间更长。所以直接把队尾扔掉，保持队列从队首到队尾单调递减（队首最大）。同理，如果求最小值，就保持单调递增。

生活中的例子：动画片点赞数（原有）

你在看动画片，屏幕最下方滚动显示过去5秒内的点赞数，要求每秒钟输出过去5秒的最大点赞数。用一个双端队列，新赞数到来时，如果比队尾大，队尾就“没用了”被移除；同时如果队首的时间戳超过了5秒，就弹出。这样每次队首就是最大值。

这个例子已经讲清楚了单调队列维护滑动窗口最大值的过程。下面我们再举一个学生更容易理解的例子。

另一个例子：篮球投篮得分

小明练习投篮，连续投了10次，每次得分记录如下。教练要求每连续3次投篮中，记录最高分。如果每次重新看3次，太麻烦。小明用一个队列：新一次投篮得分进来时，如果比队尾得分高，就把队尾移除（因为队尾以后也不可能成为这3次里的最高分了）；同时，如果队首的位置已经超出最近3次的范围，就把它弹出。这样队首总是当前窗口的最高分。

在动态规划中的应用（原有+扩展）

很多DP转移方程长这样：

dp[i] = max(dp[i-1], dp[i-2], ..., dp[i-k]) + cost[i]

比如：你要从河的一边跳到另一边，每次可以跳1~3步，每块石头上有一个收益，你想得到最大总收益。dp[i]表示跳到第i块石头时的最大总收益，它等于前面最多3块石头中的dp最大值加上当前收益。

直接算最大值需要循环k次，整个算法就是O(nk)。当n和k都很大时（比如n=10万，k=5万），就太慢了。

单调队列优化：我们维护一个队列，里面存放可能成为最大值的dp下标，并且保证下标对应的dp值从队首到队尾逐渐减小。当要计算dp[i]时：

先检查队首，如果下标已经小于i-k（超出窗口），就弹出。
此时队首就是[i-k, i-1]范围内dp最大的下标，直接用它来转移。
然后准备把当前dp[i]加入队列：如果队尾的dp值小于等于dp[i]，那么队尾就没用了（因为i更新、dp更大或相等），把它弹出。最后将i压入队尾。

这样，每次转移只需要O(1)时间，整体就是O(n)。

代码实现详解

1. 滑动窗口最大值（原有代码 + 注释补全）

下面这段代码计算长度为k的滑动窗口在每个位置的最大值，所有变量都加了中文注释：

#include <iostream>
#include <deque>
using namespace std;

int main() {
    int n = 8;                 // 数组长度
    int k = 3;                 // 窗口大小
    int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};  // 原始数组
    deque<int> dq;             // 双端队列，存储数组中元素的下标

    for (int i = 0; i < n; i++) {
        // 1. 移除超出窗口范围的队首下标（窗口左边界为 i-k+1）
        while (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();

        // 2. 保持队列单调递减：移除队尾所有比当前元素小的下标
        while (!dq.empty() && arr[dq.back()] <= arr[i])
            dq.pop_back();

        // 3. 将当前下标加入队尾
        dq.push_back(i);

        // 4. 当窗口形成（i >= k-1）时，输出队首对应的最大值
        if (i >= k - 1)
            cout << "窗口[" << i - k + 1 << "," << i << "]最大值: " << arr[dq.front()] << endl;
    }
    return 0;
}

2. 完整的DP优化示例：小青蛙跳荷叶

问题描述：池塘里有n片荷叶排成一排，每片荷叶上有一些糖果。小青蛙从第1片荷叶出发，每次可以向前跳1到k步（不能后退），到达一片荷叶后就能得到上面的糖果。问青蛙跳到第n片荷叶时，最多能得到多少糖果？

输入示例：

n=6, k=3
糖果数: [2, 5, -1, 3, 7, 4]

输出：最大总糖果数（从第1片出发，最后到达第6片）

状态定义：dp[i] 表示到达第i片荷叶时能获得的最大糖果数。 转移方程：dp[i] = max(dp[i-1], dp[i-2], ..., dp[i-k]) + candy[i]
注意：如果前面没有荷叶（i<=k），则只需要从第1片开始跳即可，但第1片是起点，所以dp[1]=candy[1]，其他需要从前面的最大值转移。

优化：用单调队列维护dp[j]的最大值，其中j在[max(1, i-k), i-1]范围内。

完整代码：

#include <iostream>
#include <deque>
#include <algorithm>  // 用于max
using namespace std;

int main() {
    int n = 6;                         // 荷叶数量
    int k = 3;                         // 最大跳跃步数
    int candy[] = {0, 2, 5, -1, 3, 7, 4}; // 糖果数，下标从1开始，便于理解

    int dp[100];                       // dp数组，足够大
    dp[1] = candy[1];                  // 起点：第1片荷叶

    deque<int> dq;                     // 单调队列，存储dp对应的下标
    dq.push_back(1);                   // 先把第1个位置入队

    for (int i = 2; i <= n; i++) {
        // 1. 移除过期的队首：下标必须 >= i-k，且是前面的位置（< i）
        while (!dq.empty() && dq.front() < i - k)
            dq.pop_front();

        // 2. 当前最优值就是队首对应的dp值
        int best = dp[dq.front()];
        dp[i] = best + candy[i];       // 状态转移

        // 3. 维护单调递减队列：移除队尾所有dp值小于等于当前dp[i]的下标
        while (!dq.empty() && dp[dq.back()] <= dp[i])
            dq.pop_back();

        // 4. 将当前下标i加入队列（待下一轮使用）
        dq.push_back(i);
    }

    cout << "最大总糖果数：" << dp[n] << endl;
    return 0;
}

运行结果：手动计算一下，得到最大总糖果数为 2 → 5 → 7 → 4 = 18（第1→2→5→6），输出应为18。

常见错误（新手容易踩的坑）

队列为空时操作 front 或 back
在while循环里用!dq.empty()判断，不要直接dq.front()，否则程序会崩溃。
忘记弹出过期的队首元素
转移前必须检查队首下标是否小于i-k，否则可能用到了窗口外的状态，导致答案错误。
维护单调性时比较的是dp值还是下标？
肯定比较dp值（或待求的值）。下标只是用来记录位置和判断是否过期。新手容易不小心比较下标大小，导致队列顺序混乱。
初始队列的处理
在第一个元素时就要把下标压入队列。有些同学会忘记，导致第一轮循环中队列为空，取front时报错。上面的代码在循环外先压入了第1个下标。
边界条件：窗口大小可能比总长度大
如果k大于n，窗口会覆盖整个数组，此时单调队列依然有效，只需要注意弹出条件i-k可能为负数，但<0的下标不会出现，所以检查dq.front() < i-k时，如果i-k<=0则不会弹出。

单调队列优化动态规划：快速找最值