图解LeetCode——862. 和至少为 K 的最短子数组（难

一、题目

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

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

二、示例

2.1> 示例 1：

【输入】nums = [1], k = 1
【输出】1

2.2> 示例 2：

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

2.3> 示例 3：

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

提示：

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

三、解题思路

根据题目描述，我们要找到N个子序列，并且要求子序列的总和要大于等于k，并且只要最短长度。那么，对于一个数组有多少子序列，我们首先需要确定数组子序列的起点。那么，由于题目中只需要最短长度，所以，假设我们以i为起点向后拼装子序列，只要子序列总和大于等于k，则立刻结束以i为起点的子序列组合行为。具体如下图所示：

为了避免不同起点执行拼装子序列会产生重复操作，所以，我们采取前缀和的方式，即：计算位置i之前的所有元素之和。以nums=[2, -1, 2, 3, 4]为例，对应的前缀和就是[0, 2, 1, 3, 6, 10]。我们通过遍历数组nums的前缀和，将某个元素i的前缀和放入到队列中，这样，从末尾执行插入，从队首执行弹出。

那么，其实对于哪些数为起点，也是有优化空间的。就是说，以下图所示，当我们发现E的前缀和sum(A-D)大于等于F的前缀和sum(A-E)，我们其实就没必要以E为起点了，因为F相比E会更适合。具体逻辑如下图所示：

四、代码实现

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int result = Integer.MAX_VALUE, n = nums.length, head = 0, tail = head;
        long[] preSum = new long[n + 1];
        /** 步骤1：构建前缀和 */
        for (int i = 0; i < n; i++) {
            if (nums[i] >= k) return 1;
            preSum[i + 1] = preSum[i] + nums[i];
        }
        /** 步骤2：构建单调栈和使用单调栈求最小值 */
        int[] queue = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            while (head != tail && preSum[queue[tail - 1]] >= preSum[i]) 
                tail--;
            queue[tail++] = i;
            while (head != tail && preSum[i] - preSum[queue[head]] >= k) 
                result = Math.min(i - queue[head++], result);
        }
        return result == Integer.MAX_VALUE ? -1 : result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」