欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-25 10:00:37
...

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

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

自己的思路:
(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;
    }