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

    int ans = N+1; // n+1 is impossible
    Deque<Integer> monoq = new LinkedList();
    for (int y = 0; y < P.length; y++) {
      // want opt(y) = largest x with P[x] <= P[y] - K
      while (!monoq.isEmpty() && P[y] - P[monoq.getLast()] <= 0) {
        monoq.removeLast();
      }
      while (!monoq.isEmpty() && P[y] - P[monoq.getFirst()] >= K) {
        ans = Math.min(ans, y - monoq.removeFirst());
      }
      // 0 < sum region < k
      monoq.addLast(y);
    }

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