862. 和至少为 K 的最短子数组（难度：困难）

题目链接：https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/

题目描述：

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解法：前缀和+单调队列

定义一个数组dp，用来存放前缀和。即dp[i] 表示 从下标0 到下标 i-1的元素之和。

前缀和：前n位的和。

这样可以将之前的一个连续子数组和转换为前缀和之差。例如，下标i到下标j子数组之和，j>i，可以表示为dp[j + 1] - dp[i]。

计算nums 的前缀和dp之后，使用暴力算法，枚举所有满足 i > j，且 dp[i] - dp[j] >= k的子数组，找到长度最短的一个。

我们利用一个双向队列deque来存放所有遍历过的下标i。

我们可以通过去除 deque 中的元素，从而提高效率。

优化点：

（1）遍历到 dp[i] 时，若左边某个 dp[j]，满足 dp[i] - dp[j] >= k，那么无论dp[i] 的右边的数字是大是小，都不可能把j作为起点，找到长度小于 i - j 的满足条件的子数组，因此 dp[j] 已经没有用，可以退出队列deque。

（2）遍历到 dp[i] 时，若左边某个 dp[j]，满足 dp[i] <= dp[j]，若后续遍历有个元素x，满足 x - dp[j] >= k，那么一定有 x - dp[i] >= k，由于 x 到 i 的距离一定是小于 j 的，因此 dp[j] 已经没有用了，可以退出队列。

代码：

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int len = nums.length;
        long[] dp = new long[len + 1];
        for (int i = 0; i < len; i++) {
            dp[i + 1] = dp[i] + nums[i];
        }

        int result = len + 1;
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i <= len; i++) {
            long temp = dp[i];
            while (!deque.isEmpty() && temp - dp[deque.peekFirst()] >= k) {
                result = Math.min(result, i - deque.pollFirst());
            }
            while (!deque.isEmpty() && dp[deque.peekLast()] >= temp) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        return result == len + 1 ? -1 : result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23