来源：算法讲解055【必备】单调队列-下 · 2026-10-20
依据：视频字幕 2000 字
单调队列维护"前缀和的下标窗口"，在 O(n) 内求出"累加和 ≥ K 的最短子数组长度"（数组含负数也成立）。
给定数组 arr（可正可负可零）和正数 K，求所有连续子数组中，累加和 >= K 的最短长度。返回长度，不存在返回 0（或 -1，按题目约定）。
关键点：数组有负数，所以不能用双指针（滑窗收缩不单调），必须用单调队列 + 前缀和。
pre[i] = arr[0] + arr[1] + ... + arr[i-1]，长度 n+1，pre[0] = 0。子数组 arr[l..r] 的和 = pre[r+1] - pre[l]。i < j 且 pre[i] >= pre[j]，那么对任何未来的右端点 r，用 j 做左端点得到的和 pre[r]-pre[j] 一定 ≥ 用 i 得到的和，而且 j 更靠右、长度更短。所以 i 永远没用了，可以弹掉。固定右端点 r（对应前缀和下标 r，即子数组以 arr[r-1] 结尾），我们要找最靠右的左端点 l，使得 pre[r] - pre[l] >= K，即 pre[l] <= pre[r] - K。
l。pre 值严格递增，下标也递增。pre 最小的（最容易满足 <= pre[r]-K），一旦队头满足条件，就弹出并记录长度 r - l。为什么弹出后不再需要它？因为对未来的 r' > r，r' - l 只会更长，而 l 已经能配上当前 r 了，未来配 r' 不会更优。所以每个左端点最多被弹出一次。pre[队尾] >= pre[新]，队尾弹掉——理由见上面"为什么能弹"。一句话直觉：队列里存的是"还有希望成为最优左端点"的下标，按 pre 值递增排好，队头最便宜，队尾最贵；新的来了把贵的、不划算的都挤掉。
pre[0..n]，pre[0]=0，pre[i]=pre[i-1]+arr[i-1]。dq（存下标），先把 0 压入（pre[0]=0 是候选左端点）。ans = INF（或 n+1）。r = 1..n： - 弹队头：while dq 非空 且 pre[r] - pre[dq.front()] >= K：ans = min(ans, r - dq.front())，dq.pop_front()。
- 弹队尾：while dq 非空 且 pre[dq.back()] >= pre[r]：dq.pop_back()。
- dq.push_back(r)。
ans == INF ? 0 : ans（按题目要求）。注意顺序：先弹队头（用当前 r 结算），再弹队尾（维护单调），最后入队。这样 r 不会自己配自己（长度 0）。
arr = [1, 1, 1, 6, 8, 2]，K = 10。pre = [0, 1, 2, 3, 9, 17, 19]。
| r | pre[r] | 弹队头（pre[r]-pre[front]>=10） | 弹队尾（pre[back]>=pre[r]） | 入队后 dq | ans |
|---|---|---|---|---|---|
| 初始 | - | - | - | [0] | INF |
| 1 | 1 | 1-0=1<10，不弹 | pre[0]=0<1，不弹 | [0,1] | INF |
| 2 | 2 | 2-0=2<10 | pre[1]=1<2 | [0,1,2] | INF |
| 3 | 3 | 3-0=3<10 | pre[2]=2<3 | [0,1,2,3] | INF |
| 4 | 9 | 9-0=9<10 | pre[3]=3<9 | [0,1,2,3,4] | INF |
| 5 | 17 | 17-0=17≥10 → ans=5-0=5，弹0；17-1=16≥10 → ans=min(5,4)=4，弹1；17-2=15≥10 → ans=min(4,3)=3，弹2；17-3=14≥10 → ans=min(3,2)=2，弹3；17-9=8<10 停 | pre[4]=9<17 | [4,5] | 2 |
| 6 | 19 | 19-9=10≥10 → ans=min(2,6-4=2)=2，弹4；19-17=2<10 停 | pre[5]=17<19 | [5,6] | 2 |
答案 2（子数组 [6,8] 或 [8,2]）。
from collections import deque
def shortest_subarray_sum_at_least_k(arr, K):
n = len(arr)
pre = [0] * (n + 1)
for i in range(n):
pre[i + 1] = pre[i] + arr[i]
dq = deque([0]) # 存下标，pre 值严格递增
ans = n + 1
for r in range(1, n + 1):
# 1) 用当前 r 结算队头能配上的左端点
while dq and pre[r] - pre[dq[0]] >= K:
ans = min(ans, r - dq[0])
dq.popleft()
# 2) 维护单调：队尾 pre 值 >= pre[r] 的都没用了
while dq and pre[dq[-1]] >= pre[r]:
dq.pop()
# 3) 入队
dq.append(r)
return 0 if ans == n + 1 else ans#include <bits/stdc++.h>
using namespace std;
// 返回累加和 >= K 的最短子数组长度；不存在返回 0
// arr 可含负数；K > 0
int shortestSubarraySumAtLeastK(const vector<int>& arr, long long K) {
int n = (int)arr.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + arr[i];
// 手写双端队列（数组模拟，比 deque 快，常数小）
vector<int> dq(n + 1);
int head = 0, tail = 0; // [head, tail) 区间
dq[tail++] = 0;
int ans = n + 1;
for (int r = 1; r <= n; ++r) {
// 1) 结算队头
while (head < tail && pre[r] - pre[dq[head]] >= K) {
ans = min(ans, r - dq[head]);
++head;
}
// 2) 维护单调递增（pre 值）
while (head < tail && pre[dq[tail - 1]] >= pre[r]) --tail;
// 3) 入队
dq[tail++] = r;
}
return ans == n + 1 ? 0 : ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; long long K;
cin >> n >> K;
vector<int> a(n);
for (auto& x : a) cin >> x;
cout << shortestSubarraySumAtLeastK(a, K) << '\n';
return 0;
}std::deque 快 2~3 倍，1e6 规模稳过。pre 用 long long（和可能爆 int）。pre[r] - pre[l] >= K 能转化成"在 l 的候选集合里找最优"。// 单调队列通用骨架：维护下标窗口，队内按值单调
// 这里以"前缀和单调递增 + 求最短子数组和 >= K"为例
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 = n + 1;
for (int r = 1; r <= n; ++r) {
while (h < t && pre[r] - pre[q[h]] >= K) ans = min(ans, r - q[h++]);
while (h < t && pre[q[t - 1]] >= pre[r]) --t;
q[t++] = r;
}
return ans == n + 1 ? 0 : ans;
}记忆口诀："先结算队头，再挤队尾，最后入队"；队列存下标，比较用值。
n=1e6、|arr[i]|=1e9 时和可达 1e15，必须 long long。K 也要 long long。r 会自己配自己，长度 0 混进答案。pre[dq[back]] >= pre[r] 用 >= 还是 >：用 >=。相等时保留靠右的（下标更大、长度更短），靠左的没优势。while 不是 if：一个 r 可能连续弹出多个队头（见样例 r=5）。K <= 0：本题约定 K 是正数。若 K 可为 0 或负，逻辑要改（K=0 时答案可能是 1，K<0 时任意非空子数组都行，答案 1 或 0）。n=0 返回 0。vector<int> q(n+1) 每次重建），别用全局数组忘了清。pre[0..n]，pre[i] 表示前 i 个元素和，子数组 arr[l..r] 对应 pre[r+1]-pre[l]。写代码时统一用 r 表示"前 r 个"，别混。pre 递减，队头找 pre[l] >= pre[r]-K 的最靠左的。或者经典做法：前缀和 + 单调栈/二分。r - q[h]（因为队列内下标递增，弹出 q[h] 时，q[h] 及其左边所有候选都能配 r？——注意这里要小心，计数题通常要配合"每个左端点被弹出时统计"）。补充：计数变形建议用"对每个 l 统计能配的 r"，或用树状数组/归并，单调队列计数要仔细推。dp[i] = min/max_{j in [i-m, i-1]} (dp[j] + cost(i,j))，把 cost 拆成 f(i)+g(j) 后，队列维护 g(j) 的最优。视频提到"DP + 单调队列在拓展课"。std::deque 且频繁 push/pop，1e6 规模可能 TLE，改数组模拟。pre 数组开 int，和溢出。ans = min(ans, ...)，只弹不记。K 读入用 int，但题面 K 可能到 1e14。题 1：arr = [2, -1, 2]，K = 3，答案是多少？为什么不能用双指针？
答案 3（整个数组和 = 3）。双指针失效：[2,-1] 和 = 1 < 3，但加上后面的 2 变成 3；收缩左端点时和可能变大（去掉 -1 反而变大），窗口和不单调，无法用"和大了就缩左"的贪心。
</details>
题 2：arr = [1, 2, 3, 4, 5]，K = 11，用单调队列手推一遍，答案是多少？
pre = [0,1,3,6,10,15]。r=5 时 pre[5]=15，15-pre[0]=15≥11 ans=5 弹0；15-pre[1]=14≥11 ans=4 弹1；15-pre[2]=12≥11 ans=3 弹2；15-pre[3]=9<11 停。答案 3（子数组 [3,4,5] 和 12，或 [4,5] 和 9 不够，[3,4,5] 是长度 3；其实 [2,3,4,5] 和 14 长度 4，[3,4,5] 长度 3 最短）。
</details>
题 3：把本题改成"求累加和 ≥ K 的最长子数组长度"（数组含负），单调队列怎么改？提示：想想队列该维护递增还是递减，队头结算条件怎么变。
求最长 → 要最靠左的合法 l。队列维护 pre 递减（队头 pre 最大），对每个 r，队头若 pre[r]-pre[front] >= K 就结算 ans = max(ans, r-front) 但不弹（因为更靠左的 l 对更长有利，但队头已经是队列里最靠左的候选了……）。补充：更稳妥的做法是"对每个 l 找最靠右的 r"，或前缀和 + 单调栈 + 二分。单调队列直接求最长要小心"弹出后丢失更优候选"，建议用"维护递减队列，队头满足条件时结算并弹出，因为弹出后长度只会更长但 l 更靠右反而更短"——这里方向容易绕晕，竞赛里求最长通常用前缀和 + 单调栈 + 二分（O(n log n)）或分治，不建议硬套单调队列。核心结论：单调队列天然适合"最短/最值"，求最长要换思路。
</details>