Задача: 861. Score After Flipping Matrix
Сложность: hard

Дан целочисленный массив nums и целое число k. Верните длину самой короткой непустой подмассива nums, сумма которого составляет как минимум k. Если такого подмассива нет, верните -1.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1], k = 1
Output: 1

👨‍💻 Алгоритм:

1⃣Создайте "моноочередь" индексов P: дек индексов x_0, x_1, ..., так чтобы P[x_0], P[x_1], ... увеличивались.

2⃣При добавлении нового индекса y, удалите x_i из конца дека, чтобы P[x_0], P[x_1], ..., P[y] увеличивались.

3⃣Если P[y] >= P[x_0] + K, то (как описано ранее) мы больше не рассматриваем этот x_0 и удаляем его из начала дека.

😎 Решение:

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        N = len(A)
        P = [0] * (N + 1)
        for i in range(N):
            P[i+1] = P[i] + A[i]

        ans = N + 1
        monoq = deque()

        for y in range(len(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)

        return ans if ans < N + 1 else -1

Ставь 👍 и забирай 📚 Базу знаний