【前缀和, 单调队列】和至少为 K 的最短子数组

题目

862. 和至少为 K 的最短子数组

---

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

示例 1：

输入：nums = [1], k = 1
输出：1

示例 2：

输入：nums = [1,2], k = 4
输出：-1

示例 3：

输入：nums = [2,-1,2], k = 3
输出：3

提示：

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5
• 1 <= k <= 10^9

解题

方法一： 前缀和 单调队列

思路

将问题从 “找出 nums 和至少为 k 的最短非空子数组” 转化为 “找出(nums的)前缀和数组中距离最近且相减至少为 k 的两数”。

维护一个 nums 的前缀和数组(prefixSumArr)，一个单调递增队列(monoDeque)，存储前缀和数组(prefixSumArr)中的索引，初始化 ans。
开始遍历前缀和数组：

• 如果队列不为空且「当前遍历到的前缀和(currPrefixSum)」 $\le$ 「队列尾部的前缀和」，说明「队列尾部的前缀和」已经有距离另一个前缀和更近且作差更大的替代品了，可以直接让它出队，原因：

  • 因为遍历是正向进行的，所以「当前遍历到前缀和」一定比「队列尾部的前缀和」更靠右，也就更靠近下一个前缀和。
  • 因为「当前遍历到前缀和」值更小，所以与另一个前缀和作差时得到的值更大，也就更容易大于等于 k，也就更有可能是一个合法解的一部分。
  • 由前两点可以得知此时「队列尾部的前缀和」已经有了更好的替代品，所以可以直接让他出队。
  • 循环，直到「当前遍历到前缀和」更小。

• 如果队列不为空且「当前遍历到前缀和」 $\ge$ 「队列头部的前缀和」+ k，说明这组前缀和是一组合法的解，把队列头部的索引出队，把它们作差表示的子数组的长度(i - monoDeque.poll())，更新 ans 使其保持有效解中的最小长度。

  • 循环，直到这「当前遍历到前缀和」与「队列头部的前缀和」作差小于 k，也就不是一组合法解了。

• 把当前索引从队尾入队。

最后，如果 ans 被更新到了小于等于 len 的长度，也就说明找到了最短子数组，直接返回 ans，反之没找到返回 -1。

代码

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int len = nums.length;
        long[] prefixSumArr = new long[len + 1];
        for (int i = 0; i < len; i++) {
            prefixSumArr[i + 1] = prefixSumArr[i] + (long) nums[i];
        }
        int ans = Integer.MAX_VALUE;
        Deque<Integer> monoDeque = new LinkedList<>();
        for (int i = 0; i < len + 1; i++) {
            int currPrefixSum = prefixSumArr[i];
            while (!monoDeque.isEmpty() &&
                   currPrefixSum <= prefixSumArr[monoDeque.peekLast()]) {
                monoDeque.pollLast();
            }
            while (!monoDeque.isEmpty() &&
                   currPrefixSum >= prefixSumArr[monoDeque.peek()] + k) {
                ans = Math.min(ans, i - monoDeque.poll());
            }
            monoDeque.offer(i);
        }
        return ans > len ? -1 : ans;
    }
}