【Leetcode】862. Shortest Subarray with Sum at Least K 862. 和至少为 K 的最短子数组
解法
滑动窗口题
当我们得到前缀和序列p时,问题转化成:对每个y,求一个最大的x使得p[y]-p[x]>=K
,记作opt(y)=x
。
- 当
x1<x2
且p[x1]>=p[x2]
时,显然opt(y)
不可能是x1
,因为它又远又大 - 当
y1<y2
且opt(y1)=x
时,x不应该被考虑,因为现在肯定有ans<=y1-x
,就算x符合条件,我们更新ans
的时候不会是有效的更新。
所以我们维护一个滑动窗口,里面包含了对于当前y,可以考虑的x
- 当队头元素满足条件,更新ans,并把队头pop出去,因为它不需要再被考虑
- 当队尾元素比
p[y]
大时,由规律1可知,对于后面的y来说,它们不可能是最优解了,所以把它们pop出去 - 最后把
y
加入窗口
最后,实现栈或队列的时候用deque比直接用list快
class Solution(object):
def shortestSubarray(self, A, K):
n = len(A)
p = [0]
for a in A:
p.append(p[-1]+a)
window = collections.deque([0])
ans = n+1
for i in xrange(1,n+1):
while window and p[i]-p[window[0]]>=K:
ans = min(ans, i-window.popleft())
while window and p[i]<=p[window[-1]]:
window.pop()
window.append(i)
return ans if ans!=n+1 else -1