Задача: 1004. Max Consecutive Ones III
Сложность: 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⃣Подсчет максимального количества последовательных единиц:
На каждом шаге обновляйте максимальное количество последовательных единиц, сравнивая текущую длину окна (разница между правым и левым указателями) с текущим максимумом.

😎 Решение:

public class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0, maxOnes = 0, zeroCount = 0;

        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }

            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }

            maxOnes = Math.max(maxOnes, right - left + 1);
        }

        return maxOnes;
    }
}

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