動機

What makes this problem hard is that we have negative values.

  • sliding window + monotone stack = monotone queue
  • prefix sum in fly + hash

Problem

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1], k = 1Output: 1

Example 2:

Input: nums = [1,2], k = 4Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3Output: 3

 

Constraints:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105
  • 1 <= k <= 109

Sol

這次有負數代表sum不會直線上升，但是題目要求至少總和為k

所以還有用sliding window的希望，不過要處理sum可能會下降的問題

monotone stack可以維持sum直線上升，所以我們要把兩個技巧結合起來

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        psum = defaultdict(int)
        q = deque([[-1,0]])
        cnt = 0
        ret = float('inf')
        
        for i,n in enumerate(nums):
            cnt += n
            
            while q and cnt - q[0][1] >= k:
                ret = min(ret, i-q.popleft()[0])
            while q and q[-1][1] >= cnt: # k >= cnt - q[-1][1]
                q.pop()
            q.append([i,cnt])
        return ret if ret != float('inf') else -1