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

🔴   🔖  队列 数组 二分查找 前缀和 滑动窗口 单调队列 堆（优先队列）  🔗 力扣 LeetCode

题目

Given an integer array nums and an integer k, return _the length of the shortest non-emptysubarray of _nums with a sum of at leastk. If there is no such subarray , return -1.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1], k = 1

Output: 1

Example 2:

Input: nums = [1,2], k = 4

Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3

Output: 3

Constraints:

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

题目大意

给你一个整数数组 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[i] 可能是负数，普通的滑动窗口方法不再适用：

• 如果 nums[i] 都是非负数，我们可以使用滑动窗口（双指针）来找到满足条件的最短子数组，因为数组和随着窗口的扩大是单调递增的。
• 但是如果 nums[i] 包含负数，数组和可能会随着窗口的扩大而减小，打破了单调性，导致滑动窗口方法无法正确处理。

为了应对 nums[i] 可能是负数的问题，引入前缀和和单调队列：

1. 前缀和的作用

• 使用前缀和数组 prefixSum 表示从数组开始到当前位置的累积和。
• prefixSum[j] - prefixSum[i] 可以直接计算出区间 [i, j) 的子数组和。

2. 单调队列的优化

• 对于一个位置 j，如果找到一个 i，使得：

  • prefixSum[j] - prefixSum[i] >= k，且
  • j - i 是满足条件的最短长度， 则可以快速得到答案。

• 使用一个单调队列（双端队列）deque 来存储前缀和的下标。单调队列维护如下性质：

  1. 队列中的前缀和的下标单调递增（保证更小的下标出现在前面）。
  2. 队列中的前缀和值严格递增（保证更大的前缀和不会被需要）。
  3. 遍历过程中，弹出所有无效的下标。

3. 具体步骤

• 计算前缀和数组。
• 遍历数组的每个位置 j，维护一个单调递增队列：
  • 弹出无效的下标：如果 prefixSum[j] - prefixSum[deque[0]] >= k，说明队首的下标可以满足条件，弹出队首并尝试更新最短长度。
  • 维护单调性：如果队列中已有的下标对应的前缀和比 prefixSum[j] 大，说明当前的前缀和更优（对应的区间更短），弹出队尾直到队列单调递增。
  • 将当前的前缀和下标 j 加入队列。
• 如果在遍历完成后仍未找到满足条件的子数组，返回 -1。

复杂度分析

• 时间复杂度：O(n)，需要遍历 nums 一次。
• 空间复杂度：O(n)，前缀和数组和单调队列都需要 O(n) 的空间。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var shortestSubarray = function (nums, k) {
	const n = nums.length;
	const prefixSum = new Array(n + 1).fill(0);

	for (let i = 0; i < n; i++) {
		prefixSum[i + 1] = prefixSum[i] + nums[i];
	}

	let deque = []; // 双端队列存储前缀和的下标
	let minLength = n + 1;

	for (let j = 0; j <= n; j++) {
		// 弹出队首直到满足条件
		while (deque.length && prefixSum[j] - prefixSum[deque[0]] >= k) {
			minLength = Math.min(minLength, j - deque.shift());
		}

		// 保持队列的单调性
		while (deque.length && prefixSum[j] <= prefixSum[deque[deque.length - 1]]) {
			deque.pop();
		}

		// 将当前下标加入队列
		deque.push(j);
	}

	return minLength === n + 1 ? -1 : minLength;
};

相关题目

题号	标题	题解	标签	难度	力扣
3095	或值至少 K 的最短子数组 I		位运算 数组 滑动窗口	🟢	🀄️ 🔗
3097	或值至少为 K 的最短子数组 II	[✓]	位运算 数组 滑动窗口	🟠	🀄️ 🔗