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

😎 Решение:

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, max_ones = 0, zero_count = 0;

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

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

            max_ones = max(max_ones, right - left + 1);
        }

        return max_ones;
    }
};

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