Max Consecutive Ones

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

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

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

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

Q: Это задача на скользящее окно?

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

Q: Как подсчитать количество последовательных единиц, если можно перевернуть один ноль?

Ведите два счётчика: длину последовательности, заканчивающейся здесь, без переворота и с уже использованным одним переворотом. При 1 оба увеличиваются на единицу. При 0 счётчик с переворотом становится равен обычному счётчику плюс один, а обычный сбрасывается до 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.

+14 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

Каждый участок где-то начинается. Поэтому попробуй каждый индекс в качестве начала и двигайся вперёд, пока встречаешь единицы; число шагов — это длина участка, начинающегося в этой точке. Наибольшее количество шагов среди всех начал и будет ответом. Для [1, 1, 0, 1, 1, 1, 0, 1] проход от начала с индексом 3 захватывает три единицы, прежде чем встретится 0 с индексом 6, поэтому результат равен 3.

Ответ верен, потому что самый длинный участок начинается с одного из проверяемых индексов, а проход от его первого индекса точно измеряет его длину.

Сложность скрывается в перекрытии. В массиве из n единиц проход от индекса 0 занимает n шагов, от следующего — n-1 и так далее, всего около n² / 2 шагов. При n = 2 × 10^4 это 2 × 10^8 шагов — слишком много для ограничения по времени в более медленных языках.

Алгоритм

Установите 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 увеличивается на единицу. Ноль завершает её, поэтому значение current сбрасывается до 0. После каждой единицы сравнивай current с best.

Для массива [1, 1, 0, 1, 1, 1, 0, 1] значение current принимает значения 1, 2, 0, 1, 2, 3, 0, 1, и наибольшее из них — 3. Длина каждой серии измеряется на её последнем индексе, где current равен её полной длине, поэтому наибольшее найденное значение — это длина самой длинной серии.

Каждое значение считывается один раз, что даёт временную сложность O(n), а для хранения данных нужны всего два целых числа.

Алгоритм

Задайте 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.
В Lua и R индексация массива начинается с 1, поэтому при проходе вперёд проверяй start + length ≤ n, а не < n.

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

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

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

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

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

Это задача на скользящее окно?

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

Как подсчитать количество последовательных единиц, если можно перевернуть один ноль?

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается