Max Consecutive Ones

Q: Какова временная сложность задачи «Максимальное количество последовательных единиц»?

Решение за один проход работает за время O(n) , потому что оно считывает каждое значение один раз, и использует O(1) дополнительной памяти: один счётчик для текущей последовательности и один для наилучшей. Перезапуск подсчёта на каждом индексе занимает O(n²) для массива, состоящего только из 1.

Q: Почему счётчик сбрасывается до 0, а не до 1?

Счётчик хранит длину последовательности, которая заканчивается на текущем индексе. Если значение в этой позиции равно 0 , там не заканчивается последовательность из единиц, поэтому её длина равна 0 . Следующая единица увеличивает его до 1 — длины новой последовательности.

Q: Является ли задача «Максимальное количество подряд идущих единиц» задачей на скользящее окно?

Можно рассматривать это как одно целое: окно содержит текущую последовательность, его правая граница сдвигается при каждом значении, а 0 перемещает левую границу за него. Окно не сужается шаг за шагом, поэтому один счётчик заменяет две границы.

НовичокМассивы и строки

+10

Тебе дан массив nums, в котором каждое значение — 0 или 1. Серия — это последовательность единиц, расположенных подряд, без 0 между ними. Верни длину самой длинной серии или 0, если в массиве нет ни одной единицы.

Функция

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: массив из 0 и 1
Возвращаетinteger: длина самой длинной последовательности подряд идущих единиц

Ограничения

1 ≤ nums.length ≤ 2 × 10⁴
Каждый nums[i] равен 0 или 1.

Примеры

Ввод: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Вывод: 3
Пояснение: Единицы образуют три серии: индексы 0–1 (длина 2), 3–5 (длина 3) и индекс 7 отдельно (длина 1). Самая длинная имеет длину 3.

Ввод: nums = [0, 1, 0, 1, 1]
Вывод: 2
Пояснение: Одиночная 1 с индексом 1 уступает паре с индексами 3 и 4, поэтому ответ — 2.

Ввод: nums = [0, 0, 0]
Вывод: 0
Пояснение: Единицы нигде нет, поэтому нет и серии, а ответ — 0.

Дополнительный вопрос

Что, если можно перевернуть не более k нулей в единицы? Какой длины может стать самая длинная последовательность и можно ли найти её за один проход?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Последовательность завершается в тот момент, когда появляется 0, поэтому для каждого индекса нужно знать только длину последовательности, заканчивающейся на нём. Один счётчик, который увеличивается при 1 и сбрасывается при 0, находит самую длинную последовательность за один проход.

Считайте вперёд от каждого индекса

Верно, но не успевает на самых больших тестах

Идея

Попробуй начать с каждого индекса и двигайся вперёд, пока встречаются единицы; число шагов — это длина последовательности, начинающейся с этого индекса. Самая длинная последовательность начинается с одного из этих индексов, поэтому ответ — наибольшее количество.

Эти проходы пересекаются. Для массива из n единиц они занимают примерно n² / 2 шагов, то есть 2 × 10^8 при n = 2 × 10^4.

Алгоритм

Установите best = 0.
Для каждого индекса start установите length = 0.
Пока start + length находится внутри массива и nums[start + length] равно 1, увеличивайте length на 1.
Оставьте большее из значений best и length.
Верните best.

def findMaxConsecutiveOnes(nums):
    n = len(nums)
    best = 0
    for start in range(n):
        length = 0
        while start + length < n and nums[start + length] == 1:
            length += 1
        best = max(best, length)
    return best

Один проход с текущим счётчиком

Идея

Храни current — длину последовательности единиц, которая заканчивается на текущем индексе. Единица увеличивает эту последовательность на один элемент; ноль завершает её, поэтому current становится равным 0. Длина каждой последовательности измеряется на её последнем индексе, где current равна её полной длине, поэтому наибольшее значение, которого достигает current, и есть ответ.

Для [1, 1, 0, 1, 1, 1, 0, 1] значения current равны 1, 2, 0, 1, 2, 3, 0, 1, а наибольшее значение — 3.

Алгоритм

Установите best = 0 и current = 0.
Для каждого значения в nums: если оно равно 1, прибавьте 1 к current и сохраните большее из значений best и current.
Если оно равно 0, установите current = 0.
Верните best.

def findMaxConsecutiveOnes(nums):
    best = 0
    current = 0
    for x in nums:
        if x == 1:
            current += 1
            best = max(best, current)
        else:
            # A 0 breaks the run.
            current = 0
    return best

Ловушки и крайние случаи

Обновлять best только при встрече с 0. Серия, которая доходит до конца, как в [0, 1, 1], никогда не записывается. Обновляйте после каждой 1 или выполняйте ещё одно сравнение после цикла.
Не сбрасывать current при встрече с 0. Отдельные серии складываются, и [1, 1, 0, 1, 1] возвращает 4.
Задавать начальное значение best равным 1 или nums[0]. Для [0, 0, 0] должно возвращаться 0.
В Lua и R, где индексация массивов начинается с 1, ограничивать проход вперёд условием < n вместо ≤ n. Последнее значение никогда не считывается, поэтому [0, 1] возвращает 0.

Частые вопросы3

Какова временная сложность задачи «Максимальное количество последовательных единиц»?

Решение за один проход работает за время O(n), потому что оно считывает каждое значение один раз, и использует O(1) дополнительной памяти: один счётчик для текущей последовательности и один для наилучшей. Перезапуск подсчёта на каждом индексе занимает O(n²) для массива, состоящего только из 1.

Почему счётчик сбрасывается до 0, а не до 1?

Счётчик хранит длину последовательности, которая заканчивается на текущем индексе. Если значение в этой позиции равно 0, там не заканчивается последовательность из единиц, поэтому её длина равна 0. Следующая единица увеличивает его до 1 — длины новой последовательности.

Является ли задача «Максимальное количество подряд идущих единиц» задачей на скользящее окно?

Можно рассматривать это как одно целое: окно содержит текущую последовательность, его правая граница сдвигается при каждом значении, а 0 перемещает левую границу за него. Окно не сужается шаг за шагом, поэтому один счётчик заменяет две границы.

def findMaxConsecutiveOnes(nums):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

nums = [1, 1, 0, 1, 1, 1, 0, 1]

Ожидаемый вывод