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 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k

一开始写法写成了最大连续子数组，写错了

class Solution {
    public int shortestSubarray(int[] A, int K) {
        //最大连续子序列
        int ans = -1,sum = 0,last = 0;
        for(int i=0;i<A.length;i++){
            sum+=A[i];
            if(sum>=K){
                if(ans==-1) ans = i - last + 1;
                else ans = Math.min( ans , i - last + 1);
            }
            if(sum<=0){
                sum = 0;
                last = i;
            }
        }
        return ans;
    }
}

这是网友提供的答案
https://cloud.tencent.com/developer/article/1505345

class Solution{
    public int shortestSubarray(int[] A, int K) {
        ArrayDeque<Integer> dq = new ArrayDeque<>();

        int minLength = Integer.MAX_VALUE;

        int[] sum = new int[A.length + 1];
        //前缀和数组
        for(int i = 1; i <= A.length; ++i){
            sum[i] = sum[i - 1] + A[i - 1];
        }

        for(int i = 0; i< sum.length;++i){
            if(i != 0 ){
                while(dq.size() > 0 && sum[dq.peekLast()] >= sum[i]){
                    dq.pollLast();
                }

                while(dq.size() > 0 && sum[i] - sum[dq.peekFirst()] > K){
                    minLength = Math.min(minLength, i - dq.pollFirst());
                }
            }

            dq.addLast(i);
        }

        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}