你好，同学！欢迎来到 NOI 提高组数据结构专项训练。

今天我们要攻克的是单调队列（Monotonic Queue）家族中最具技巧性的题目之一：和至少为 K 的最短子数组。这道题是“滑动窗口最大值”的高阶变体，也是理解“单调性优化”如何应对负数干扰的绝佳教材。

一、 预备知识点

在挑战本题前，请确保你已经掌握：

1. 前缀和（Prefix Sum）：将子数组和转化为两个前缀和之差：$Sum(i, j) = P[j] - P[i]$。
2. 单调队列（Monotonic Queue）：一种维护元素单调性且支持双端弹出的特殊队列。
3. 双指针与滑动窗口：理解为什么在有负数存在时，简单的双指针滑动窗口会失效。

二、 NOI 竞赛题目描述

题目名称：和至少为 K 的最短子数组 (Shortest Subarray with Sum at Least K) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个长度为 $n$ 的整数数组 $A$，以及一个整数 $k$。 请你找出 $A$ 中和至少为 $k$ 的最短、非空子数组的长度。如果不存在这样的子数组，返回 $-1$。

【输入格式】 第一行包含两个整数 $n$ 和 $k$。 第二行包含 $n$ 个整数，表示数组 $A$ 的元素。

【输出格式】 输出一个整数，表示满足条件的最短子数组的长度。如果不存在，输出 $-1$。

【样例输入】

3 3
2 -1 2

【样例输出】

3

(解释：整个数组 [2, -1, 2] 的和为 3，长度为 3。虽然 [2] 和 [2] 也是子数组，但由于中间有 -1，它们不满足和至少为 3)

【数据规模与约定】

• $1 \le n \le 10^5$
• $-10^5 \le A[i] \le 10^5$
• $1 \le k \le 10^9$

三、 启发式思路引导：草稿纸上的推演

请拿出草稿纸，随我一起推演：

1. 转化模型

求最短的 $(j - i)$ 使得 $P[j] - P[i] \ge k$，其中 $P$ 是前缀和数组，$j > i$。

2. 为什么双指针失效？

在普通滑动窗口中，我们假设窗口右移和变大必导致和增加。但本题有负数！前缀和 $P$ 不是单调递增的。当 $P[j]$ 减小时，左指针向右移动可能反而让 $P[j]-P[i]$ 变得更小，从而错失解。

3. 单调队列的“生存法则”

假设我们正在考虑以 $j$ 作为子数组的终点，我们要从之前存下的 $P[i]$ 中找一个最靠右（距离 $j$ 最近）且 $P[i] \le P[j] - k$ 的。

• 法则一（排除过时解）：如果某个 $P[i]$ 已经满足了 $P[j] - P[i] \ge k$，那么这个 $i$ 以后再也不用看了。因为即使后续的 $j' > j$ 也能满足条件，由于 $j' - i > j - i$，它产生的长度一定不是最短的。
• 法则二（维护单调性）：如果当前的前缀和 $P[j]$ 小于或等于队列末尾的 $P[q.back()]$，那么旧的末尾就彻底没用了。
  • 理由：$P[j]$ 相比旧末尾更小（更容易满足减法条件），且位置更靠右（生成的长度更短）。

四、 复杂度分析与时间复杂度优化建议

• 时间复杂度：$O(n)$。 每个前缀和下标只会入队一次、出队一次。虽然内部有 while 循环，但均摊下来每个元素的操作次数是常数级。
• 空间复杂度：$O(n)$。 需要存储前缀和数组以及单调队列。

优化建议：

1. 前缀和范围：由于 $A[i]$ 可达 $10^5$，$n$ 为 $10^5$，前缀和必须开 long long 以防溢出。
2. deque 效率：在 NOI 竞赛中，如果数据量达到 $10^6$ 以上，std::deque 性能不如手动模拟数组队列：int q(MAXN), head=0, tail=0;。
3. 初值判断：结果 ans 初始值应设为 $n+1$，最后判断是否被更新。

五、 算法流程图（伪代码逻辑）

在 Mermaid 流程图中，我们使用括号表达逻辑，规避特殊字符报错。

graph TD
    Start(开始处理任务) --> Init(计算前缀和数组 P, 初始化双端队列 dq)
    Init --> Loop(遍历下标 j 从 0 到 n)
    Loop -- 结束 --> CheckResult{ans 是否大于 n}
    CheckResult -- 是 --> ReturnNeg1(返回 -1)
    CheckResult -- 否 --> ReturnAns(返回 ans)
    
    Loop -- 当前前缀和 P_j --> Rule1{循环: P_j 减去 队首前缀和 是否大于等于 k}
    Rule1 -- 成立 --> UpdateAns(更新 ans 为 min_ans 和 j减队首下标 的较小值)
    UpdateAns --> PopFront(弹出队首元素)
    PopFront --> Rule1
    
    Rule1 -- 不成立 --> Rule2{循环: P_j 是否小于等于 队尾前缀和}
    Rule2 -- 成立 --> PopBack(弹出队尾元素)
    PopBack --> Rule2
    
    Rule2 -- 不成立 --> Push(将下标 j 压入队尾)
    Push --> Next(准备处理下一个下标)
    Next --> Loop

六、 读题关键词总结

在 NOI 竞赛中，通过以下词汇快速锁定“单调队列优化前缀和”：

1. “最短 / 最长”：暗示最优化问题。
2. “连续子数组”：前缀和的典型场景。
3. “和至少为 K”：不等式约束。
4. “存在负数”：这是区分普通滑动窗口与单调队列的关键标志。

教练寄语： 同学，记住单调队列的核心：“如果一个候选人比你更强（值更优）还比你更年轻（位置更优），你就永远没机会出头了。” 这种“优胜劣汰”的思想，是解决所有单调性问题的基石。去实现它吧！