Java | LeetCode
Задача: 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 {
public int shortestSubarray(int[] A, int K) {
int N = A.length;
long[] P = new long[N + 1];
for (int i = 0; i < N; ++i)
P[i + 1] = P[i] + A[i];
int ans = N + 1;
Deque<Integer> monoq = new LinkedList<>();
for (int y = 0; y < P.length; ++y) {
while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()])
monoq.removeLast();
while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K)
ans = Math.min(ans, y - monoq.removeFirst());
monoq.addLast(y);
}
return ans < N + 1 ? ans : -1;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 441 ·