线性动态规划：统计和至少为K的最短子数组长度

题目描述：
给定一个整数数组 nums`` 和一个整数 k，你需要找到该数组中和至少为 k的**最短非空连续子数组**的长度。如果不存在这样的子数组，返回-1`。子数组定义为原数组中连续的一段。

示例 1：
输入：nums = [2, -1, 2], k = 3
输出：3
解释：子数组 [2, -1, 2] 的和为 3，长度为 3，是最短的。

示例 2：
输入：nums = [1, 2], k = 4
输出：-1
解释：没有和至少为 4 的子数组。

解题过程循序渐进讲解

这个问题虽然看起来可以通过暴力枚举所有子数组解决（时间复杂度 O(n²)），但我们可以用更优的方法——前缀和 + 单调队列，在 O(n) 时间内解决。这本质上是一种线性动态规划的变体，利用单调性优化状态转移。

步骤 1：理解子数组和与前缀和的关系

设数组长度为 n。
定义前缀和数组 prefix，其中：

prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

约定 prefix[0] = 0，那么子数组 nums[i..j] 的和可以表示为：

sum(i, j) = prefix[j+1] - prefix[i]

其中 0 <= i <= j < n。

问题转化为：找到一对 (i, j) 使得 prefix[j+1] - prefix[i] >= k 且 j - i + 1 最小。

步骤 2：基本思路

对于每个右端点 r = j+1（即前缀和下标），我们想找一个左端点 l = i 使得：

prefix[r] - prefix[l] >= k

即：

prefix[l] <= prefix[r] - k

并且 r - l 尽量小（因为子数组长度为 r - l）。

如果我们固定 r，那么满足条件的 l 是那些前缀和不超过 prefix[r] - k 的下标。为了让 r - l 最小，我们要在这些可选的 l 中选择最大的那个下标。

步骤 3：暴力法的问题

如果对每个 r，我们都去遍历所有 l < r 来寻找最大的 l 满足 prefix[l] <= prefix[r] - k，时间复杂度是 O(n²)。
但注意，随着 r 增大，prefix[r] 会变化，我们需要快速找到这样的 l。

一个自然的想法是：
维护一个候选左端点列表，其中的前缀和是单调递增的（为什么？因为如果 l1 < l2 且 prefix[l1] >= prefix[l2]，那么对于未来的 r，l1 永远不会比 l2 更优，因为 l2 更靠后且前缀和更小，更容易满足 prefix[l] <= prefix[r] - k）。

步骤 4：使用单调队列维护候选左端点

我们维护一个双端队列 deque，里面存放的是左端点的下标 l，并且保证这些下标对应的 prefix[l] 是单调递增的。

算法流程：

1. 初始化 prefix[0] = 0，ans = n+1（一个大于 n 的值表示无穷大）。
2. 遍历 r 从 0 到 n（r 是前缀和下标，对应子数组右边界是 r-1）：
   • 将 prefix[r] 与队列尾部下标对应的前缀和比较，如果 prefix[队列尾部下标] >= prefix[r]，就弹出队尾（因为它不可能比当前 r 更优）。
   • 将 r 加入队尾。
   • 从队头开始检查：如果 prefix[r] - prefix[队头] >= k，说明队头这个左端点与当前右端点 r 组成的子数组满足条件，更新答案 ans = min(ans, r - 队头)，然后弹出队头（因为对于更大的 r，即使队头还能满足条件，子数组长度也会更大，不是最短，所以可以放心弹出）。
3. 遍历结束后，如果 ans 仍为初始值，返回 -1，否则返回 ans。

为什么弹出队头不影响正确性？
因为如果当前队头 l 满足条件，那么对于更大的 r，即使 l 仍满足条件，子数组长度 r - l 只会更大，不会比当前找到的长度更短，所以可以丢弃。

步骤 5：举例演示

以 nums = [2, -1, 2], k = 3 为例：

• 前缀和：prefix = [0, 2, 1, 3]
• 队列变化（存下标）：
  • r=0: 队列=[0]
  • r=1: prefix[1]=2，队尾0对应prefix=0<2，不弹出，加入1 → 队列=[0,1]
  • r=2: prefix[2]=1，队尾1对应prefix=2>=1，弹出1；队尾0对应prefix=0<1，加入2 → 队列=[0,2]
  • r=3: prefix[3]=3，队尾2对应prefix=1<3，加入3 → 队列=[0,2,3]
    检查队头0：prefix[3]-prefix[0]=3 >=3，更新ans=3-0=3，弹出0 → 队列=[2,3]
    检查队头2：prefix[3]-prefix[2]=2<3，停止。
• 最终 ans=3。

步骤 6：复杂度分析

• 每个下标最多入队一次、出队一次，所以总操作次数 O(n)。
• 空间复杂度 O(n) 用于前缀和数组和队列。

步骤 7：代码实现（Python示例）

from collections import deque

def shortestSubarray(nums, k):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    
    dq = deque()
    ans = n + 1
    for r in range(len(prefix)):
        # 维护队列单调递增
        while dq and prefix[dq[-1]] >= prefix[r]:
            dq.pop()
        dq.append(r)
        # 检查队头是否满足条件
        while dq and prefix[r] - prefix[dq[0]] >= k:
            ans = min(ans, r - dq.popleft())
    return ans if ans <= n else -1

关键点总结：

1. 利用前缀和将子数组和转化为两个前缀和的差。
2. 维护一个前缀和单调递增的双端队列，队列中存放的是可能的左端点。
3. 对于每个右端点，从队头尝试满足条件并更新答案，满足条件后的左端点可以直接丢弃，因为它不会再产生更短的子数组。
4. 这个解法本质上是动态规划思想的单调队列优化，避免了不必要的状态转移。