🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1493. Longest Subarray of 1's After Deleting One Element
Сложность: medium
Дан бинарный массив nums, из которого следует удалить один элемент.
Верните размер самой длинной непустой подмассивы, содержащей только 1, в результирующем массиве. Верните 0, если такого подмассива не существует.
Пример:
Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].
👨💻 Алгоритм:
1⃣Инициализация переменных:
zeroCount для подсчёта нулей в текущем окне, longestWindow для хранения максимальной длины окна, содержащего не более одного нуля, и start для левой границы окна.
2⃣Итерация по массиву:
При каждом элементе увеличиваем zeroCount, если это ноль.
Если zeroCount превышает 1, сокращаем окно, перемещая левую границу вправо и уменьшая zeroCount, пока количество нулей не станет меньше или равно 1.
Обновляем longestWindow текущей длиной окна i - start.
3⃣ Возврат результата:
Вернуть longestWindow.
😎 Решение:
public class Solution {
public int LongestSubarray(int[] nums) {
int zeroCount = 0;
int longestWindow = 0;
int start = 0;
for (int i = 0; i < nums.Length; i++) {
if (nums[i] == 0) {
zeroCount++;
}
while (zeroCount > 1) {
if (nums[start] == 0) {
zeroCount--;
}
start++;
}
longestWindow = Math.Max(longestWindow, i - start);
}
return longestWindow;
}
}
Ставь 👍 и забирай 📚 Базу знаний