Лучший отрезок
длины k

Категория

Алгоритм

Уровень

Начальный

Опирается на

Глава 9.3: сдвиг окна; глава 9.2: контракт и примеры

Зачем это знать

Задача КТП и LeetCode 643 — типичные задачи на окно

§1Условие задачи

Условие уточнено в главе 9.2, здесь оно записано в окончательном виде. Во всех примерах главы используется тот же список посещений по часам, что в главах 9.1 и 9.3.

§2Лучшее окно на ходу

Задачу можно решить готовой функцией из главы 9.3: посчитать все суммы и выбрать наибольшую. Время O(n), но список сумм занимает O(n) памяти, а нужна из него одна сумма.

def best_window_via_sums(nums, k):
    sums = window_sums(nums, k)          # ValueError — внутри window_sums
    best = max(sums)
    return (sums.index(best), best)    # index — первое вхождение

Лучшую сумму можно не хранить в списке, а обновлять сразу после каждого сдвига. Вместо списка sums — две переменные: best, лучшая сумма среди уже пройденных окон, и start, начало этого окна.

1. Первое окно. total = sum(nums[:k]). Пока оно единственное, оно же лучшее: best = total, start = 0.
2. Сдвиг. Для каждого r от k до n − 1: total += nums[r] − nums[r − k], как в главе 9.3.
3. Сравнение. Если total строго больше best, запомнить: best = total, start = r − k + 1 — это начало окна, которое заканчивается на r.
4. Ответ. После цикла вернуть (start, best).

Обе детали правила — «строго больше» и «начать с первого окна» — следуют из ответов интервьюера в главе 9.2. Что происходит, если записать их иначе, показано в §5 и §6.

§3Сборка функции и песочница

Функция отличается от window_sums тремя строками: вместо списка ответа — best и start, вместо записи в список — сравнение. Расставьте десять строк по порядку.

>>> total, r, k = 50, 6, 3
>>> best, start = total, r - k + 1
>>> best, start
(50, 4)

Напишите функцию сами в окне ниже. Восемь тестов — это примеры из главы 9.2 и сравнение с перебором срезов на двухстах случайных списках. Часть тестов заготовка проходит сразу.

§4Код и пошаговый прогон

def best_window(nums, k):
    if k < 1 or k > len(nums):
        raise ValueError("k должно быть от 1 до len(nums)")
    total = sum(nums[:k])
    best, start = total, 0
    for r in range(k, len(nums)):
        total += nums[r] - nums[r - k]
        if total > best:
            best, start = total, r - k + 1
    return (start, best)

Прогон на списке посещений. Голубые ячейки — окно после сдвига. В таблице переменных видно, как best и start меняются на шагах 7, 11 и 18 и остаются прежними на шаге 14, когда сумма 45 оказалась меньше лучшей 47.

§5Равные суммы: знак сравнения

Интервьюер в главе 9.2 ответил, что при равных суммах нужно самое левое окно. Окна проходятся слева направо, поэтому первое из окон с наибольшей суммой встречается раньше остальных. Чтобы его не заменило окно правее с той же суммой, сравнение должно быть строгим. Ниже обе версии запущены на [5, 1, 5, 1] с k = 2: все три окна дают сумму 6.

Если бы интервьюер попросил самое правое окно, верной была бы как раз версия с >=. Знак сравнения — это запись ответа на вопрос о равных суммах, поэтому вопрос задают до кода.

§6Отрицательные числа: начальное значение

Вторая ошибка — начать с best = 0, как будто сумма не бывает меньше нуля. Пока в списке есть окно с положительной суммой, ответ получается верным, и ошибка незаметна. Обе версии запущены на [-5, -2, -8, -1] с k = 2: суммы окон −7, −10, −9.

Есть и другой распространённый вариант — best = float("-inf"), минус бесконечность: любая сумма больше неё. Он тоже верен, но сумма первого окна уже посчитана, и начать с неё проще: не нужен особый объект и start сразу имеет смысл.

§7Наибольшее среднее, LeetCode 643

В LeetCode 643 нужно вернуть наибольшее среднее отрезка длины k. Среднее — это сумма, делённая на k, а k одно для всех окон. Поэтому окно с наибольшим средним — то же, что окно с наибольшей суммой, и задача решается одной строкой поверх best_window. Делить сумму каждого окна не нужно: делится только ответ.

def find_max_average(nums, k):
    start, best = best_window(nums, k)
    return best / k

>>> find_max_average([1, 12, -5, -6, 50, 3], 4)
12.75
>>> find_max_average([5], 1)
5.0

Первый вызов — пример из условия LeetCode: лучшее окно [12, −5, −6, 50], сумма 51, среднее 51 / 4 = 12,75. Оператор / в Python всегда даёт число с плавающей точкой, поэтому во втором вызове получается 5.0. В LeetCode 643 числа бывают отрицательными, и ошибка с best = 0 из §6 там тоже приводит к неверному ответу.

§8Счётчик в окне, LeetCode 1456

Состояние окна не обязательно сумма чисел. В LeetCode 1456 дана строка и число k, нужно найти наибольшее число гласных в подстроке длины k. Состояние окна — счётчик гласных count. При сдвиге пришедшая гласная прибавляет 1, ушедшая — вычитает 1. Остальное устроено так же, как в best_window.

def max_vowels(s, k):
    vowels = set("aeiou")
    count = sum(1 for ch in s[:k] if ch in vowels)
    best = count
    for r in range(k, len(s)):
        count += (s[r] in vowels) - (s[r - k] in vowels)
        best = max(best, count)
    return best

>>> sum(1 for ch in "abc" if ch in "aeiou")
1
>>> True - False, False - True, True - True
(1, -1, 0)

Прогон на примере из условия LeetCode: строка "abciiidef", k = 3, ответ 3 — окно "iii". В прогоне строка передана списком букв, чтобы показать каждую букву в своей ячейке; код работает и со строкой. На шагах 5 и 17 счётчик не меняется: гласная пришла, и гласная ушла.

Здесь best обновляется через max: начало окна в этой задаче не нужно, достаточно числа, и отдельный if не требуется. Напишите функцию сами.

§9Проверьте себя