Участник:Лукьянов Кирилл/Shortest Subarray with Sum at Least K

Материал из DISCOPAL
Перейти к: навигация, поиск


https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k

 
class Solution(object):
 
    def shortestSubarray(self, A, K):
        N = len(A)
        P = [0]
        for x in A:
            P.append(P[-1] + x)
        ans = N+1
        monoq = collections.deque()
        for y, P[y] in enumerate(P):
            while monoq and P[y] <= P[monoq[-1]]:
                monoq.pop()
            while monoq and P[y] - P[monoq[0]] >= K:
                ans = min(ans, y - monoq.popleft())
            monoq.append(y)
        if ans < N+1:
            return ans  
        else:
            return -1