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. 1 <= A.length <= 50000

2. -10 ^ 5 <= A[i] <= 10 ^ 5

3. 1 <= K <= 10 ^ 9

分析

单调递增栈。 找左边比右边小的，左边i比右边j大的无用，

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        B = [0]
        for i in A:
            B.append(B[-1]+i)
        s = []
        res = float('inf')
        for i,b in enumerate(B):
            if not s:
                s.append(i)
            else:
                while s and B[s[-1]] > b: s.pop() #useless, pop out
                while s and B[s[0]] <= b - K: 
                    res = min(res,i - s[0])
                    s.pop(0)
                s.append(i)
        return res if res!= float('inf') else -1