Сложность: medium
Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.
Пример:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
👨💻 Алгоритм:
1⃣Инициализация оконного подхода:
Используйте два указателя для создания скользящего окна. Инициализируйте левый указатель в начале массива, правый указатель будет двигаться по массиву. Создайте переменную для подсчета количества нулей в текущем окне.
2⃣Перемещение правого указателя и обновление окна:
Перемещайте правый указатель по массиву, обновляя количество нулей в текущем окне. Если количество нулей превышает k, сдвиньте левый указатель вправо до тех пор, пока количество нулей снова не станет допустимым (меньше или равно k).
3⃣Подсчет максимального количества последовательных единиц:
На каждом шаге обновляйте максимальное количество последовательных единиц, сравнивая текущую длину окна (разница между правым и левым указателями) с текущим максимумом.
😎 Решение:
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
left = 0
max_ones = 0
zero_count = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
while zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
max_ones = max(max_ones, right - left + 1)
return max_ones
Ставь 👍 и забирай 📚 Базу знаний