LeetCode刷题【862】 和至少为 K 的最短子数组

返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。

如果没有和至少为 K 的非空子数组，返回 -1 。

示例 1：

输入：A = [1], K = 1
输出：1

示例 2：

输入：A = [1,2], K = 4
输出：-1

示例 3：

输入：A = [2,-1,2], K = 3
输出：3

提示：

1. 1 <= A.length <= 50000
2. -10 ^ 5 <= A[i] <= 10 ^ 5
3. 1 <= K <= 10 ^ 9

题解

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int[] sum = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            if (k <= nums[i]){
                return 1;
            }
            sum[i+1] = nums[i] + sum[i];
        }
        //前缀和数组sum
        int res = Integer.MAX_VALUE;
        Deque<Integer> queue = new LinkedList<>();
        for(int i=0;i<sum.length;i++){
            while(!queue.isEmpty()&&sum[i]<=sum[queue.peekLast()]) {
                queue.pollLast();
            }
            while(!queue.isEmpty()&&sum[i]-sum[queue.peek()]>=k) {
                res = Math.min(res,i-queue.poll());
            }
            queue.add(i);
        }
        return res==Integer.MAX_VALUE?-1:res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)