LeetCode862-和至少为K的最短子数组

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

中文链接：https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/

题目详述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

题目详解

  • 对数组求前缀和，得到数组 s，那么 s[i] - s[j] 就代表区间 [j + 1, i] 的和。
  • 遍历前缀和数组，维护一个从队首到队尾单调递增的队列。运用当前元素减去队首元素来计算是否满足条件，若满足则更新结果，并弹出队首元素，这是因为之后如果再用到队首元素，答案也不是最优。
  • 比较当前元素与队尾元素，维持队列单调递增，这是因为若 q[q.back] <- q[i] <- … <- q[future="" id]，则当="" `q[future="" id]="" -="" q[d.back()]="">= k && q[d.back()] >= q[i]，必有q[future id] - q[i] >= k`，说明不单调的队尾是不需要的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_00862 {

    public int shortestSubarray(int[] A, int K) {
        int n = A.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + A[i];
        }
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(0);
        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= n; ++i) {
            while (!deque.isEmpty() && s[i] - s[deque.peekFirst()] >= K) {
                res = Math.min(res, i - deque.pollFirst());
            }
            while (!deque.isEmpty() && s[i] <= s[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);
        }
        return res != Integer.MAX_VALUE ? res : -1;
    }
}