Re: [閒聊] 每日leetcode

[dont (dont)]

862. Shortest Subarray with Sum at Least K

## 思路

nums裡面有負數
所以先算prefix_sum, 用prefix差值計算subarray的和

維護一個mono-increasing的Deque記錄index
如果頭尾的prefix差值超過k就pop並更新res

## Code

```python
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:

        prefix = [0] * (len(nums)+1)
        for i in range(len(nums)):
            prefix[i+1] = prefix[i] + nums[i]

        res = float('inf')
        queue = deque() # mono-increasing

        for i in range(len(nums)+1):

            while queue and prefix[queue[-1]] >= prefix[i]:
                queue.pop()

            while queue and prefix[i] - prefix[queue[0]] >= k:
                res = min(ans, i - queue.popleft())

            queue.append(i)

        return res if res != float('inf') else -1
```

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.205.4 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731809163.A.D03.html