862. Shortest Subarray with Sum at Least K

[tech-cow]

862. Shortest Subarray with Sum at Least K

'''

思路参考：https://github.com/Shellbye/Shellbye.github.io/issues/41
Time: O(N^2) TLE 

Brute Force + preSum 思路：
在Brute Force的基础上，加入一个PreSum来记忆化记忆一下到i为止的和，方便与之后直接调用

注意的事项就是要给preSum多预留一个位置，和DP类似，用来处理一些edge case，比如array总长就一个

Input: A = [1], K = 1
Output: 1
    
这个例子如果用 preSum[j] - preSum[i] 而不预留位置, preSum则为[1] ，由于两个位置重叠，减后的0
应该是给与额外的preSum位置，preSum则为[0, 1] 这样及时相减也能够得到1。 (1 - 0)
另外就是i和j的for循环分别多走一位，为了匹配多出来的一位preSum

'''

class Solution(object):
    def shortestSubarray(self, nums, target):
        preSum = [0]
        globalMin = float('inf')
        
        for num in nums:
            preSum.append(preSum[-1] + num)
        
        for i in range(len(nums) + 1):
            for j in range(i, len(nums) + 1):
                if preSum[j] - preSum[i] >= target:
                    globalMin = min(globalMin, j - i)    
        
        return globalMin if globalMin != float('inf') else -1

'''
Time: O(N)
Space: O(N)


两个While Loop

第一个While Loop用于滑动窗口的中的，移动左边指针的操作
当preSum[i]减去queue里面最左边，也就是queue里面最小的index的时候(因为queue里存的是index，所以是升序排序的，queue[0]就可以理解为最小的数)
    如果满足超过target大小，我们保存在globalMin并且可以开始移动左边的指针了，所以这里queue.popleft掉了最左边的指针。

    
第二个While Loop用来删掉负数
    如果在preSum的数组里面，当前的preSum[i]要大于之前加进去的数的话，比如preSum[2] = 100, preSum[3] = 50, 说明从2-3的过程中，sum小了50，所以是加到了-50，加了一个负数。
    我们为了求取最小的subarray，负数的就要果断移除
'''


from collections import deque
class Solution(object):
    def shortestSubarray(self, nums, target):
        globalMin = float('inf')
        preSum = [0]
        for num in nums:
            preSum.append(preSum[-1] + num)
        
        queue = deque()
        for i in range(len(nums) + 1):
            while queue and preSum[i] - preSum[queue[0]] >= target:  
                globalMin = min(globalMin, i - queue.popleft())  
                
            while queue and preSum[queue[-1]] >= preSum[i]:
                queue.pop()
            queue.append(i)
        return globalMin if globalMin != float('inf') else -1