1
# 1. we can not use sliding window to solve the problem, because the numbers in nums can be negative,
2
# the numbers in sliding window are not always incrementing
3
# ex [8,-4,3,1,6], 10
4

5
# 2. prefixsum2 - prefixsum1 >= k is used to find a subarray whose sum >= k.
6
# 3. monotonic queue is used to keep the prefix sums are in the incrementing order
7
# 4. If the diffenence between the cur and the tail of monotonic queue is greater than or equal to k, we can find the shortest length of the subarray at this time.
8

9

10
class Solution:
11
    def shortestSubarray(self, nums: List[int], k: int) -> int:
12
        prefixsum = [0]
13
        monoq = deque()
14
        minLen = float("inf")
15
        # to calculate prefix sum
16
        for n in nums:
17
            prefixsum.append(n + prefixsum[-1])
18
        for idx, cur in enumerate(prefixsum):
19
            while monoq and prefixsum[monoq[-1]] >= cur:
20
                monoq.pop()  # to maintain monotonic queue
21

22
            # If the diffenence between the head and the tail of monotonic queue is greater than or equal to k, we can find the shortest length of the subarray at this time.
23
            while monoq and cur - prefixsum[monoq[0]] >= k:
24
                minLen = min(minLen, idx - monoq.popleft())
25
            monoq.append(idx)
26
        return -1 if minLen == float("inf") else minLen