Минимальный отрезок
с суммой не меньше S

Категория

Алгоритм

Уровень

Начальный

Опирается на

Глава 10.3: расширение и сжатие; глава 10.2: контракт и примеры

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

Задача КТП и LeetCode 209 из программы Top Interview 150

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

Условие уточнено в главе 10.2, здесь оно записано в окончательном виде. В главе используются два списка из таблицы примеров той же главы: заказы магазина по часам и пример из условия LeetCode 209.

Условие допустимости — total >= s. Окно, для которого оно выполнено, дальше называется подходящим.

§2Сжатие подходящего окна

В главе 10.3 искали самый длинный отрезок. Расширение там могло сделать окно недопустимым, и цикл while сжимал окно, пока оно снова не становилось допустимым. Здесь нужен самый короткий отрезок, и роли меняются. Расширение приближает окно к подходящему: сумма растёт. Когда окно стало подходящим, его сжимают, чтобы проверить, останется ли оно подходящим при меньшей длине.

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

1. Расширение. Правая граница r сдвигается на один элемент: total += nums[r].
2. Запись и сжатие. Пока окно подходит, то есть пока total >= s, длина окна r − l + 1 сравнивается с лучшей. Затем левый элемент убирается: total -= nums[l], l += 1.
3. Ответ. После цикла for вернуть лучшую длину или 0, если подходящего окна не было.

Отличия от схемы главы 10.3 собраны в таблице. Строки расширения и сжатия те же, меняются условие цикла и место, где записывается длина.

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

§3Проход вручную

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

После первых пяти расширений сумма равна 48, и окно сжимается четыре раза подряд. Записанные длины — 5, 4, 3, 2. Тот же проход показан в блоке главы 10.1.

§4Сборка цикла и песочница

Начало функции написано: проверка s и три переменные — best = 0, total = 0, l = 0. Ниже девять строк остальной части. Длина окна сначала кладётся в переменную length, затем сравнивается с лучшей. Расставьте строки по порядку.

>>> best, length = 0, 4
>>> best == 0 or length < best
True
>>> best, length = 4, 3
>>> best == 0 or length < best
True
>>> best, length = 3, 3
>>> best == 0 or length < best
False

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

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

def shortest_window(nums, s):
    if s < 1:
        raise ValueError("s должно быть не меньше 1")
    best = 0
    total = 0
    l = 0
    for r in range(len(nums)):
        total += nums[r]
        while total >= s:
            length = r - l + 1
            if best == 0 or length < best:
                best = length
            total -= nums[l]
            l += 1
    return best

Прогон на примере 2: список [2, 3, 1, 2, 4, 3], порог 7. В нём стоит проследить за тремя местами. На шагах 16–21 найдено первое подходящее окно длины 4, оно записано и сжато. На шагах 25–35 окно сжимается два раза подряд, длина уменьшается до 3. На шагах 44–47 сумма окна [4, 3] равна порогу точно, и в best попадает ответ 2.

Оценка времени та же, что в главе 10.3: правая граница сдвигается n раз, левая — не больше n раз за весь проход, всего не больше 2·n сдвигов. Цикл while останавливается без отдельной проверки l <= r: сумма пустого окна равна 0, а порог не меньше 1. Поэтому нужна проверка s в первой строке. При s = 0 условие total >= s было бы истинно и для пустого окна. Тогда на непустом списке индекс l вышел бы за его конец, и функция закончилась бы исключением IndexError.

§6Место записи и знак в условии цикла

Первая ошибка — перенести в эту задачу схему главы 10.3 без изменений и записывать длину после цикла while. Вторая — поставить в условии цикла строгий знак. Обе версии запущены на примере 2 и возвращают число, исключений нет. Верный ответ — 2.

Верная версия — прогон в §5. Первую ошибку находят тесты песочницы test_example, test_exact_sum, test_whole_list, test_no_window и сравнение с перебором, вторую — test_exact_sum, test_whole_list, test_zeros и сравнение с перебором. На примере 1 вторая версия возвращает верный ответ 2: сумма лучшего отрезка заказов равна 32, это строго больше порога. Поэтому пример с суммой точно на пороге записан в таблицу главы 10.2 отдельной строкой.

§7Начальное значение ответа

В задаче на самый длинный отрезок ответ начинается с 0 и растёт через max. Здесь ответ уменьшается, и перенести тот же приём с заменой max на min нельзя. Ниже версия, в которой три строки записи заменены одной: best = min(best, r - l + 1), а начальное значение осталось best = 0.

В верной версии число 0 в переменной best означает «подходящего окна ещё не было». Настоящая длина подходящего окна не меньше 1, поэтому спутать эти значения нельзя. Интервьюер в главе 10.2 попросил вернуть 0, если отрезка нет, и это значение возвращается без преобразования.

Распространён и другой вариант: начать с бесконечности, best = float("inf"). Любая длина меньше неё, поэтому работает запись через min. Но бесконечность нельзя вернуть как ответ, и последняя строка функции должна её заменить: return 0 if best == float("inf") else best.

>>> best = float("inf")
>>> 4 < best
True
>>> best = min(best, 4)
>>> best
4
>>> min(float("inf"), 3)
3
>>> float("inf") == float("inf")
True

Оба варианта верны. В модуле используется первый: в нём последняя строка функции — return best без преобразования.

§8Отправка на LeetCode 209

В LeetCode 209 та же задача записана с другим порядком параметров: сначала порог target, затем список. Числа на сайте положительные, порог не меньше 1, список не пустой, поэтому все входы сайта укладываются в контракт из §1. Ниже функция с именем и параметрами сайта вызывает shortest_window на трёх примерах из условия.

>>> def minSubArrayLen(target, nums):
...     return shortest_window(nums, target)
...
>>> minSubArrayLen(7, [2, 3, 1, 2, 4, 3])
2
>>> minSubArrayLen(4, [1, 4, 4])
1
>>> minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1])
0

Ответы совпадают с ответами из условия: 2, 1 и 0. На сайте функция записана методом класса Solution, поэтому при отправке тело shortest_window переносят в метод minSubArrayLen(self, target, nums) и заменяют имя s на target.

§9Счётчик в окне, LeetCode 1004

Состояние окна не обязательно сумма. В LeetCode 1004 дан массив из нулей и единиц и число k. Нужно найти наибольшее число единиц подряд, которое получится, если заменить единицами не больше k нулей. В главе 10.2 задача пересказана так: найти самый длинный отрезок, в котором нулей не больше k. Массив при этом не меняется.

Это задача на самый длинный отрезок, поэтому схема взята из главы 10.3 целиком. Меняется состояние окна: вместо суммы — счётчик нулей zeros. Пришедший ноль увеличивает счётчик на 1, ушедший — уменьшает. Условие допустимости — zeros <= k, условие цикла — его отрицание.

def longest_ones(nums, k):
    best = 0
    zeros = 0
    l = 0
    for r in range(len(nums)):
        if nums[r] == 0:
            zeros += 1
        while zeros > k:
            if nums[l] == 0:
                zeros -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Прогон на списке [1, 0, 1, 1, 0, 1, 0, 1] с k = 1, ответ 4. На шагах 24–31 в окно пришёл второй ноль, и окно сжимается два раза: первый раз уходит единица, счётчик не меняется, и только после ухода нуля окно снова допустимо. На шагах 40–50 сжатий три.

Сравнение с функцией longest_within показывает, какие строки в решении общие для всех задач на самый длинный отрезок, а какие зависят от задачи.

Три вызова ниже — два примера из условия LeetCode и случай k = 0, в котором ответ — самая длинная серия единиц.

>>> longest_ones([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2)
6
>>> longest_ones([0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], 3)
10
>>> longest_ones([1, 1, 0, 1, 1, 1], 0)
3

Напишите функцию сами. Семь тестов: два примера с сайта, k = 0, список из одних нулей, k больше числа нулей, пустой список и сравнение с перебором.

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