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

链接：862.和至少为K的最短子数组
难度：Hard
标签：队列、数组、二分查找、前缀和、滑动窗口、单调队列、堆（优先队列）
简介：返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。

题解 1 - typescript

• 编辑时间：2021-07-21
• 执行用时：6080ms
• 内存消耗：50.3MB
• 编程语言：typescript
• 解法介绍：单调递增队列。

function shortestSubarray(nums: number[], k: number): number {
  const n = nums.length;
  const queue: number[] = [];
  const sums = [0];
  let sum = 0;
  nums.forEach(num => sums.push((sum += num)));
  let ans = Infinity;
  for (let i = 0; i <= n; i++) {
    const sum = sums[i];
    while (queue.length && sums[queue[queue.length - 1]] > sum) queue.pop();
    for (const prevIndex of queue) {
      if (sum - sums[prevIndex] >= k) {
        ans = Math.min(ans, i - prevIndex);
      } else break;
    }
    queue.push(i);
  }
  return ans === Infinity ? -1 : ans;
}

题解 2 - typescript

• 编辑时间：2021-07-21
• 执行用时：2896ms
• 内存消耗：50.3MB
• 编程语言：typescript
• 解法介绍：优化题解 1。

function shortestSubarray(nums: number[], k: number): number {
  const n = nums.length;
  const queue: number[] = [];
  const sums = [0];
  let sum = 0;
  nums.forEach(num => sums.push((sum += num)));
  let ans = Infinity;
  for (let i = 0; i <= n; i++) {
    const sum = sums[i];
    let p = -1;
    while (queue.length && sum - sums[queue[0]] >= k) p = queue.shift()!;
    if (p !== -1) ans = Math.min(ans, i - p);
    while (queue.length && sums[queue[queue.length - 1]] > sum) queue.pop();
    queue.push(i);
  }
  return ans === Infinity ? -1 : ans;
}

题解 3 - cpp

• 编辑时间：2022-10-26
• 执行用时：204ms
• 内存消耗：102.3MB
• 编程语言：cpp
• 解法介绍：前缀和+单调递增队列，遍历到一个值时，可以快速知道前面的前缀和。

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0x7fffffff;
        vector<long long> sums(1 + n, 0);
        for (int i = 0; i < n; i++) sums[i + 1] = sums[i] + nums[i];
        deque<int> q;
        q.push_back(0);
        for (int i = 0; i < n; i++) {
            int idx = -1;
            while (q.size() && sums[i + 1] - sums[q.front()] >= k) idx = q.front(), q.pop_front();
            if (idx != -1) ans = min(ans, i + 1 - idx);
            while (q.size() && sums[q.back()] > sums[i + 1]) q.pop_back();
            q.push_back(i + 1);
        }
        return ans == 0x7fffffff ? -1 : ans;
    }
};