title
给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。
示例 1：
输入：nums = [1], k = 1
输出：1
示例 2：
输入：nums = [1,2], k = 4
输出：-1
示例 3：
输入：nums = [2,-1,2], k = 3
输出：3
提示：
1 <= nums.length <= 105-105 <= nums[i] <= 1051 <= k <= 109
solution
单调队列
'''
主要是去除无用数据，维护右端点
可以单调栈二分，也可以单调队列
参考: https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/solution/liang-zhang-tu-miao-dong-dan-diao-dui-li-9fvh/
'''
class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
ans = float('inf')
n = len(nums)
pre = [0]
for v in nums:
pre.append(pre[-1] + v)
import collections
q = collections.deque()
# 单调队列，j< i, 向右, 如果s[i] - s[j] >= k, j则不会再作为可作为答案的左端点了; 递增队列 对于s[j] >= s[i], 则j也可以舍弃
for i, v in enumerate(pre):
while q and pre[q[-1]] >= v:
q.pop()
q.append(i)
while q and v - pre[q[0]] >= k:
ans = min(ans, i - q[0])
q.popleft()
return ans if ans != float('inf') else -1
# 单调栈 + 二分
class BinarySearch:
# If you wanna binary search big integer, plz set data range, which can be used as same as big integer low and high
# find the first index that value >= val
def bisect_left(data, val, l=None, r=None, key=None):
if l is None or r is None:
l, r = 0, len(data) - 1
if key is None:
key = lambda x: data[mid]
while l <= r:
mid = (l + r) // 2
if key(mid) >= val:
r = mid - 1
else:
l = mid + 1
return l
class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
ans = float('inf')
pre = [0]
for v in nums:
pre.append(pre[-1] + v)
# print(pre)
q = []
# 单调递增栈， 栈上二分
for i, v in enumerate(pre):
while q and pre[q[-1]] >= v:
q.pop()
q.append(i)
t = BinarySearch.bisect_left(q, True, key=lambda x: v - pre[q[x]] < k)
if t - 1 >= 0:
ans = min(ans, i - q[t - 1])
return ans if ans != float('inf') else -1