862.Shortest-Subarray-with-Sum-at-Least-K

862. Shortest Subarray with Sum at Least K

题目地址

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

题目描述

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

Example 1:
Input: A = [1], K = 1
Output: 1

Example 2:
Input: A = [1,2], K = 4
Output: -1

Example 3:
Input: A = [2,-1,2], K = 3
Output: 3

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

代码

Approach #1 Sliding Window

Time: O(N) && Space: O(N)

class Solution {
  public 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]; // prefix sum
    }

    int ans = N + 1;
    Deque<Integer> monoq = new LinkedList();

    for (int y = 0; y < P.length; y++) {
      while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()]) {
        monoq.removeLast(); // decreasing sequence
      }

      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;
  }
}

#2

public int shortestSubarray(int[] A, int K) {
  int N = A.length;
  int res = N + 1;
  int[] B = new int[N + 1];
  for (int i = 0; i < N; i++)     B[i + 1] = B[i] + A[i];
  Deque<Integer> d = new ArrayDeque<>();
  for (int i = 0; i < N + 1; i++) {
      while (d.size() > 0 && B[i] - B[d.getFirst()] >=  K)
          res = Math.min(res, i - d.pollFirst());
      while (d.size() > 0 && B[i] <= B[d.getLast()])
          d.pollLast();
      d.addLast(i);
  }
  return res <= N ? res : -1;
}