单调队列（下）

来源：算法讲解055【必备】单调队列-下　·　2026-10-20

依据：视频字幕 2000 字

一句话概括

单调队列维护"前缀和的最小值候选集"，对每个右端点 O(1) 摊还地找到最靠右的、满足 pre[i] - pre[j] >= K 的左端点 j，从而 O(n) 求出"和 ≥ K 的最短子数组"。

它解决什么问题

给定数组 a（可正可负可零）和正数 K，求所有连续子数组中，累加和 ≥ K 的最短长度。暴力是 O(n²) 枚举左右端点，单调队列把它压到 O(n)。

推广地说：当你在枚举右端点 i、需要在左侧候选集里找"满足某个单调性条件的最优 j"时，单调队列就是那把刀。本题的条件是 pre[i] - pre[j] >= K，等价于 pre[j] <= pre[i] - K，而我们要 j 尽量大（这样长度 i-j 最短）。

基础知识（前置概念，用大白话解释）

前缀和：pre[0]=0，pre[i] = a[0]+...+a[i-1]（这里用 0 下标、pre 长度 n+1 的写法）。子数组 [j, i-1] 的和 = pre[i] - pre[j]。
子数组必须连续：所以"以 i 结尾"的子数组，左端点 j 只能在 [0, i-1] 里挑。
单调队列：一个双端队列，队内存的是下标，对应的值（这里是 pre 值）从队头到队尾严格递增。支持：队尾 push 时弹掉所有 ≥ 新值的元素；队头 pop 掉过期/不再需要的元素；队头就是当前最优候选。
为什么能弹：如果 j1 < j2 且 pre[j1] >= pre[j2]，那么 j1 永远比 j2 差——j1 更靠左（长度更长）且前缀和更大（更不容易满足 pre[j] <= pre[i]-K），所以 j1 可以永久扔掉。

原理（为什么这么做是对的，尽量给直觉）

枚举右端点 i（1..n）。对每个 i，我们要在 j ∈ [0, i-1] 中找最大的 j 使得 pre[j] <= pre[i] - K。

关键观察：pre 值大的 j 是"坏"的。如果 j1 < j2 但 pre[j1] >= pre[j2]，那 j1 在任何未来时刻都不会比 j2 更优（j2 更靠右、门槛更低）。所以维护一个pre 值严格递增的下标队列，队头就是"pre 最小"的候选。

但我们要的是最大的 j，不是最小的 pre。怎么办？——因为队列里 pre 严格递增，从队头往队尾扫，pre 越来越大，j 也越来越大。我们要找"pre[j] <= pre[i]-K 的最靠右的 j"，就是队列里最后一个满足条件的元素。

这里有个精妙的处理：从队头开始弹。只要队头满足 pre[队头] <= pre[i]-K，就把它弹掉并记录答案（长度 i - 队头）。为什么可以弹？因为队头是最靠左的，它满足了，说明"以 i 结尾"存在合法解；但队头太靠左，长度不优。弹掉它之后，新的队头更靠右，如果也满足，答案更短——继续弹。弹到不满足为止，最后一次弹掉的那个就是最靠右的合法 j（因为队列 pre 递增，不满足的都在后面）。

等等，这里要小心：弹掉队头后，队头变成更靠右的 j，如果它也满足，答案更短，继续弹——这是对的。但如果新的队头不满足呢？那就停，此时刚才弹掉的那个就是答案。所以逻辑是：while 队头满足条件：记录答案 = i - 队头，弹出队头。循环结束时，最后记录的那个就是最短的。

（补充说明：这里"弹掉队头"是安全的，因为对于未来的 i' > i，pre[i'] - K >= pre[i] - K，门槛只会更松，队头既然现在满足，未来也满足，但它作为左端点只会让长度更长，所以永远不需要它了。）

然后把 i 入队前，从队尾弹掉所有 pre[队尾] >= pre[i] 的元素（它们比 i 更靠左且 pre 更大，永远劣于 i）。

步骤（编号，可照着写）

计算前缀和 pre[0..n]，pre[0]=0。
初始化双端队列 dq，先放入 0（pre[0]=0 的下标）。
初始化 ans = INF。
对 i = 1..n：

a. 弹队头：while dq 非空且 pre[dq.front()] <= pre[i] - K：ans = min(ans, i - dq.front())；dq.pop_front()。

b. 弹队尾：while dq 非空且 pre[dq.back()] >= pre[i]：dq.pop_back()。

c. 入队：dq.push_back(i)。

返回 ans == INF ? -1 : ans（题目若保证有解则直接返回 ans）。

注意顺序：先弹队头（用 i 作为右端点结算），再弹队尾、再入队。这样 i 不会自己跟自己配对（子数组长度至少 1）。

样例（一个具体小例子，带每步变化）

数组 a = [1, 1, 1, 6, 8, 2]，K = 10。pre = [0, 1, 2, 3, 9, 17, 19]。

|---|--------|---------------|---------------------|--------------|------------|

| 初始 | - | - | - | - | [0] |

| 1 | 1 | -9 | 无（pre[0]=0 > -9） | [0] | [0,1] |

| 2 | 2 | -8 | 无 | [0,1] | [0,1,2] |

| 3 | 3 | -7 | 无 | [0,1,2] | [0,1,2,3] |

| 4 | 9 | -1 | 无（pre[0]=0 > -1） | [0,1,2,3] | [0,1,2,3,4] |

| 5 | 17 | 7 | 弹 0（ans=5-0=5），弹 1（ans=4），弹 2（ans=3），弹 3（ans=2）；pre[4]=9>7 停 | [4] | [4,5] |

| 6 | 19 | 9 | 弹 4（ans=min(2, 6-4=2)=2）；pre[5]=17>9 停 | [5] | [5,6] |

最终 ans = 2。验证：子数组 [6,8]（下标 3..4）和 = 14 ≥ 10，长度 2；[8,2] 和 = 10，长度 2。正确。

代码

Python（好读，用于理解）

from collections import deque

def shortest_subarray_sum_at_least_k(a, K):
    n = len(a)
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + a[i]

    dq = deque([0])          # 存下标，pre 值严格递增
    ans = float('inf')

    for i in range(1, n + 1):
        # 1) 弹队头：只要满足 pre[j] <= pre[i]-K，就结算并弹出
        while dq and pre[dq[0]] <= pre[i] - K:
            ans = min(ans, i - dq[0])
            dq.popleft()
        # 2) 弹队尾：pre 值 >= pre[i] 的永远劣于 i
        while dq and pre[dq[-1]] >= pre[i]:
            dq.pop()
        # 3) 入队
        dq.append(i)

    return -1 if ans == float('inf') else ans

C++（竞赛风，可直接抄）

#include <bits/stdc++.h>
using namespace std;

// 返回和 >= K 的最短子数组长度；无解返回 -1
// a 可正可负可零，K > 0
int shortestSubarraySumAtLeastK(const vector<int>& a, long long K) {
    int n = (int)a.size();
    vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + a[i];

    // 手写双端队列（比 std::deque 快，常数小）
    vector<int> dq(n + 1);
    int head = 0, tail = 0;   // [head, tail) 区间
    dq[tail++] = 0;

    int ans = INT_MAX;
    for (int i = 1; i <= n; ++i) {
        // 1) 弹队头：满足 pre[j] <= pre[i]-K 就结算并弹出
        while (head < tail && pre[dq[head]] <= pre[i] - K) {
            ans = min(ans, i - dq[head]);
            ++head;
        }
        // 2) 弹队尾：pre 值 >= pre[i] 的永远劣于 i
        while (head < tail && pre[dq[tail - 1]] >= pre[i]) {
            --tail;
        }
        // 3) 入队
        dq[tail++] = i;
    }
    return ans == INT_MAX ? -1 : ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> a = {1, 1, 1, 6, 8, 2};
    cout << shortestSubarraySumAtLeastK(a, 10) << "\n"; // 2
    return 0;
}

复杂度

时间：O(n)。每个下标最多入队一次、出队一次，摊还 O(1)。
空间：O(n)（前缀和数组 + 队列）。
常数：很小。手写数组队列比 std::deque 快约 2~3 倍，1e6 规模毫无压力。前缀和用 long long 防溢出（a 值大或 n 大时 int 会炸）。

竞赛里什么时候用（看到什么题面特征就该想到它）

题面出现"连续子数组 / 子段"+"和 / 平均值 / 乘积（取对数后）"+"≥ / ≤ 某值"+"最短 / 最长"。
前缀和 + 双指针失效（因为元素有负数，前缀和不单调），但条件可以写成 pre[j] <= pre[i] - K 这种"左端点门槛随 i 单调"的形式。
更一般地：DP 转移里出现 dp[i] = min/max over j<i of (dp[j] + f(i-j)) 且 j 的可行区间随 i 单调移动——这是单调队列优化 DP 的典型信号（本题是它的热身版）。

竞赛模板（C++，可直接背下来）

// 单调队列求"和 >= K 的最短子数组"
// 输入：a[0..n-1]，K>0；输出：最短长度，无解 -1
int solve(const vector<int>& a, long long K) {
    int n = a.size();
    vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + a[i];

    vector<int> q(n + 1);
    int h = 0, t = 0;
    q[t++] = 0;
    int ans = INT_MAX;

    for (int i = 1; i <= n; ++i) {
        while (h < t && pre[q[h]] <= pre[i] - K) {
            ans = min(ans, i - q[h]);
            ++h;
        }
        while (h < t && pre[q[t - 1]] >= pre[i]) --t;
        q[t++] = i;
    }
    return ans == INT_MAX ? -1 : ans;
}

边界与易错点（WA 的常见原因，越具体越好）

前缀和溢出：a 值可达 1e9、n 可达 1e6，pre 必须 long long；K 也建议 long long。
先弹队头还是先弹队尾：必须先弹队头结算（用 i 当右端点），再弹队尾、再入队。如果先入队 i，i 可能自己跟自己配对，长度算成 0。
队列初始化：必须先把下标 0（pre=0）放进去，否则左端点 j=0 的情况漏掉。
弹队头用 <= 不是 <：条件是 pre[j] <= pre[i]-K（题目是"大于等于 K"），写成 < 会漏掉恰好等于 K 的解。
弹队尾用 >=：pre 值相等时也要弹掉旧的（更靠左的更差）。
ans 初值：用 INT_MAX 或 n+1，别用 0；最后判无解。
多测清空：如果多组数据，pre、q、h、t、ans 全部重置。用 vector 局部变量最省心。
空数组 / n=0：直接返回 -1。
K ≤ 0：题目一般保证 K>0；若 K≤0，任何非空子数组都满足，答案恒为 1（除非 n=0）。

同类题 / 变形（说清楚怎么改）

和 ≤ K 的最长子数组：把 pre 取负，条件变成 pre[j] >= pre[i] - K，队列改成 pre 值递减（弹队尾用 <=），弹队头用 >=。或者直接对称改写。
和 ≥ K 的最长：不能弹队头（弹了就丢了更靠左的候选），要改成"队头不满足就停，满足也不弹"——但这样就不是 O(n) 了。正确做法是维护 pre 递减队列，找"最靠左的满足 pre[j] <= pre[i]-K 的 j"，即队尾方向找。这是经典变形，注意方向。
和恰好等于 K 的最长/最短：用哈希表存 pre 值第一次/最后一次出现的位置，O(n)，不用单调队列。
滑动窗口最大值/最小值（上节课内容）：队列存值单调，弹队头按"下标过期"（i - q[h] >= window_size）。
DP 优化：dp[i] = min_{j in [i-m, i-1]} (dp[j]) + w[i] 这类"窗口内取最值"的转移，直接套单调队列模板，把 pre 换成 dp。
二维/环形：环形数组先复制一份接在后面，长度限制 n；二维先枚举行区间压成一维。

常见坑

把"最短"和"最长"的弹队头逻辑搞混：最短 → 弹队头（越弹越优）；最长 → 不能随便弹队头。
用 std::deque 且频繁 front()/back()，常数大，1e6 可能 TLE；手写数组队列。
前缀和下标从 0 开始但队列里放的是"pre 的下标"，长度算 i - j 而不是 i - j + 1（因为 pre 是 n+1 长度，子数组 [j, i-1] 长度就是 i-j）。
忘记 ios::sync_with_stdio(false)，cin 读 1e6 个数慢一倍。
多测时 vector<long long> pre(n+1) 每次重新分配，能接受；但如果卡常数，可以全局开数组手动清。

拓展（变体、实际用途、面试常问）

面试高频：LeetCode 862「和至少为 K 的最短子数组」就是本题原题，Hard，标准答案就是单调队列 + 前缀和。面试官常追问"为什么元素有负数时双指针不行"——因为前缀和不单调，窗口收缩方向不确定。
实际用途：网络流量里找"最短的、累计超过阈值的连续时间段"；金融里找"最短的、累计收益达标的时间窗口"。
理论联系：本题是"前缀和 + 单调队列"这一组合的原型。更一般的框架是"离线查询 + 单调栈/队列"，比如"对每个 i 求最靠右的 j 使 pre[j] <= pre[i]-K"可以用单调栈 + 二分做（O(n log n)），但单调队列因为 i 单调递增所以能 O(n)。
和单调栈的区别：单调栈解决"下一个更大/更小"，单调队列解决"窗口内最值 / 带单调门槛的最优左端点"。本题门槛 pre[i]-K 随 i 单调递增（因为 pre[i] 不一定单调……等等，pre[i] 不单调！）——注意：本题能 O(n) 的真正原因是"弹掉的队头永远不再需要"，而不是门槛单调。这是个容易讲错的点，面试时别说错。

自测 3 题

题 1：a = [2, -1, 2]，K = 3，答案是多少？用上面的算法手动跑一遍队列。

答案

pre = [0, 2, 1, 3]。

i=1, pre=2, 门槛 -1：队头 0 的 pre=0 > -1，不弹。弹队尾：pre[0]=0 < 2，不弹。队列 [0,1]。
i=2, pre=1, 门槛 -2：队头 0 的 pre=0 > -2，不弹。弹队尾：pre[1]=2 >= 1，弹 1。队列 [0]，入队 2 → [0,2]。
i=3, pre=3, 门槛 0：队头 0 的 pre=0 <= 0，ans = 3-0 = 3，弹 0。队头 2 的 pre=1 > 0，停。弹队尾：pre[2]=1 < 3，不弹。入队 3 → [2,3]。

答案 = 3。验证：整个数组和 = 3 ≥ 3，长度 3；子数组 [2,-1,2] 只有它自己满足（[2,-1]=1, [-1,2]=1, [2]=2, [-1]=-1, [2]=2 都不够）。正确。

</details>

题 2：把题目改成"和 ≤ K 的最长子数组"，描述算法思路（不用写完整代码）。

答案

令 b[i] = -a[i]，K' = -K，则"和 ≤ K"等价于"b 的和 ≥ -K = K'"。但"最长"不能直接套上面的模板（上面求最短靠弹队头）。

正确做法：维护 pre 的严格递减队列（弹队尾用 <=），对每个 i，在队列里从队尾往前找第一个满足 pre[j] >= pre[i] - K 的 j（因为递减队列从队头到队尾 pre 越来越小，从队尾找就是找"最靠左的满足条件的"——不对，要仔细想）。

更稳的思路：和 ≤ K 的最长 = 对每个 i 找最靠左的 j 使 pre[j] >= pre[i]-K。维护 pre 递减队列（队头 pre 最大、最靠左）。对每个 i，如果队头满足 pre[队头] >= pre[i]-K，则队头就是最靠左的合法 j（因为队头最靠左且 pre 最大最容易满足），记录 ans = max(ans, i - 队头)，但不弹队头（它可能对未来的 i 还有用，因为未来门槛 pre[i']-K 可能更大，队头可能不再满足，但更靠右的 j 可能满足——所以不能弹）。

实际上标准做法是：从队尾弹（维护递减），然后对每个 i 用二分在队列里找最靠左的满足 pre[j] >= pre[i]-K 的位置。O(n log n)。或者用"从队头弹但只弹不满足的"——不行，会丢候选。

最简洁的正确做法：预处理 pre 的后缀最大值 + 双指针。因为要找最靠左的 j 使 pre[j] >= pre[i]-K，等价于在 [0, i-1] 里找最左的满足条件的 j。维护一个"pre 的递减栈"（从栈底到栈顶 pre 递减、下标递增），对每个 i 在栈里二分找最左满足 pre[j] >= pre[i]-K 的 j。O(n log n)。

（这题是 LeetCode 962 的变体思路，面试常考"为什么最长不能 O(n) 单调队列"——因为弹队头会丢掉更靠左的候选，而最长恰恰要最靠左。）

</details>

题 3：给定 a = [1, -1, 1, -1, 1, -1, 1]，K = 1，答案是多少？说明为什么"双指针滑动窗口"在这题会错。

答案

pre = [0, 1, 0, 1, 0, 1, 0, 1]。

i=1, pre=1, 门槛 0：队头 0 的 pre=0 <= 0，ans=1，弹 0。队列空，入队 1 → [1]。
i=2, pre=0, 门槛 -1：队头 1 的 pre=1 > -1，不弹。弹队尾：pre[1]=1 >= 0，弹 1。入队 2 → [2]。
i=3, pre=1, 门槛 0：队头 2 的 pre=0 <= 0，ans=min(1, 3-2=1)=1，弹 2。入队 3 → [3]。
i=4, pre=0, 门槛 -1：队头 3 的 pre=1 > -1，不弹。弹队尾：pre[3]=1 >= 0，弹 3。入队 4 → [4]。
i=5, pre=1, 门槛 0：队头 4 的 pre=0 <= 0，ans=1，弹 4。入队 5 → [5]。
i=6, pre=0, 门槛 -1：队头 5 的 pre=1 > -1，不弹。弹队尾：pre[5]=1 >= 0，弹 5。入队 6 → [6]。
i=7, pre=1, 门槛 0：队头 6 的 pre=0 <= 0，ans=1，弹 6。入队 7 → [7]。

答案 = 1（单个元素 1 就满足 ≥ 1）。

双指针为什么错：滑动窗口收缩依赖"窗口和关于左端点单调"——即"左端点右移，窗口和单调减"。但这里元素有负数，右移左端点窗口和可能增大（比如窗口 [1,-1,1]，去掉 1 变成 [-1,1]，和从 1 变成 0，确实减；但窗口 [1,-1]，去掉 1 变成 [-1]，和从 0 变成 -1，也减……换个例子：窗口 [-1, 1, -1, 1]，和 0，去掉 -1 变成 [1,-1,1] 和 1，增大了）。所以双指针的"收缩到不满足为止"会漏解或死循环。必须用前缀和 + 单调队列。

</details>