LeetCode题解——862.Shortest Subarray with Sum at Least K

中文题目
官方答案，时间复杂度O(n)

自己的思路：
（1）暴力，超时了。
（2）opt(i,k)：长度为i的数组，找和至少为k的连读子数组的长度。opt(i,k)=min{1+opt(i-1,k-A[i]), opt(i-1,K)}，结果是失败的，要连续；故写成两种递归，若选了该值，后面都要选，不然不连续；修改后，还是超时，这是自上而下，且没用辅助数组存储结果，但是想想好像没法存，是两个变量（i和k）控制，可能重叠的问题太少了。

官方解答：
（1）P[i] 是前i项的和，任何一段连续子数组都可以通过P[y] - P[x] 得到。
（2）目标opt(y) : P[x]<=P[y]-K，找最小的x。
考虑两种情况：
1）若x1<x2，且P[x1]>=P[x2]，则最终的结果肯定选的是x2，因为选了x2，让子串长度更短。
P[x1]<=P[y]-K,P[x2]<=P[y]-K，选x2。
2）若P[x]<=P[y1]-K,P[x]<=P[y2]-K，且y1

 public static int shortestSubarray(int[] A, int K) {
        int N = A.length;
        long[] P = new long[N + 1];
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + (long) A[i];

        // Want smallest y-x with P[y] - P[x] >= K
        int ans = N + 1; // N+1 is impossible
        Deque<Integer> monoq = new LinkedList(); //opt(y) candidates, as indices of P

        for (int y = 0; y < P.length; ++y) {
            // Want opt(y) = largest x with P[x] <= P[y] - K;
            // 如果P[x1]P[x2]都进去,那么一定选的是P[x2],而不会选P[x1],所以P[x1]直接弹出去
            while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()])
                monoq.removeLast();
            // 判断和队首元素相减,是不是大于等于K,是的话求一下长度,比较一下
            // 弹出队首,因为已经是最短的了,后面的P[y]若满足,也是更长的
            while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K)
                ans = Math.min(ans, y - monoq.removeFirst());

            monoq.addLast(y);
        }

        return ans < N + 1 ? ans : -1;
    }