Алгоритмы с нуля
Классическая жадность: прыжки и заправки
Ты стоишь в начале ряда камней, на каждом написано как далеко с него можно прыгнуть. Можешь ли ты добраться до последнего камня? Инстинкт говорит “перебери все пути” — но это ветвится экспоненциально. Жадный трюк в том чтобы перестать думать о путях и отслеживать одно число: самый дальний камень на котором ты мог бы стоять к этому моменту. Проходи слева направо; если этот фронтир хоть раз отстанет от твоей текущей ноги, ты застрял. Один проход, без возвратов. Тот же инстинкт «измени-одно-число» взламывает и вторую классику — поездку по круговой дороге с заправками — где весь вопрос сводится к «хватит ли топлива в сумме, и откуда стартовать?» Этот урок закрывает раздел жадности двумя задачами-завсегдатаями собеседований, обе O(n).
После этого урока ты можешь решить две знаменитые жадные задачи и объяснить локальную величину которую отслеживает каждая. Для Jump Game (прыжков) ты можешь решить достижим ли последний индекс одним проходом, поддерживая самый дальний достижимый индекс; ты можешь сформулировать тест провала (“если текущий индекс хоть раз обгоняет фронтир, ты застрял”) и обосновать почему одно число заменяет перебор каждого пути. Для Jump Game II ты можешь сосчитать минимум прыжков жадным BFS-подобным расширением по уровням: каждый “уровень” это множество индексов достижимых текущим числом прыжков, и ты тратишь прыжок ровно когда исчерпываешь текущий уровень. Для Gas Station (заправок) ты можешь сформулировать условие выполнимости (круговой маршрут возможен тогда и только тогда, когда суммарный газ >= суммарной стоимости) и найти старт сбрасывая кандидата на старт каждый раз когда текущий бак уходит в минус — и ты можешь обосновать почему сброс безопасен (ни одна пропущенная заправка тоже не могла быть верным стартом). Ты можешь показать что все три работают за O(n) время и O(1) дополнительной памяти. Это последний урок раздела жадности; следующий раздел уходит от жадности к новому шаблону.
Jump Game: отслеживай самый дальний достижимый индекс
Тебе дан массив nums где nums[i] это максимальная длина прыжка с индекса i. Начиная с индекса 0, можешь ли ты добраться до последнего индекса? Полный перебор изучает каждый выбор прыжка — экспоненциально. Жадное озарение: тебе никогда не нужно знать какой путь привёл тебя куда-то, только как далеко ты можешь быть. Так что неси одно число, farthest = наибольший индекс достижимый до сих пор.
Проходи i слева направо. На каждом шаге происходят две вещи:
- Проверка достижимости. Если
i > farthest, то никакой более ранний индекс не мог запустить тебя наi. Есть разрыв который ты не можешь пересечь — верниfalse. (Ты стоишь на камне которого фронтир так и не достиг.) - Продвинь фронтир. Иначе
iдостижим, так что сiты можешь прыгнуть вплоть доi + nums[i]. Обновиfarthest = max(farthest, i + nums[i]).
Если проход завершается ни разу не провалив проверку, последний индекс был достижим — верни true. (Равносильно: остановись рано в тот момент когда farthest >= n - 1.)
Вот проход на [2, 3, 1, 1, 4]. Смотри как farthest растёт и заметь что он всегда остаётся на уровне i или впереди него:
index i : 0 1 2 3 4
nums[i] : 2 3 1 1 4
| |
i+nums : 2 4 3 4 8
farthest: 2 4 4 4 8 <- frontier, monotonically non-decreasing
^^^^^^^^^^^^^^^^^^^^
i <= farthest at every step -> reachable, return trueФронтир достигает индекса 4 (последнего индекса) уже на i = 1. Единственное число farthest подытожило каждый возможный путь — это и есть вся жадная идея.
Почему одного числа достаточно. Достижимость “монотонна”: если индекс j достижим и j <= farthest, то достижимо и всё между старым фронтиром и j + nums[j]. Нет дыр позади фронтира которые нужно посещать заново. Так что максимальный охват это полная сводка того где ты можешь быть; ничего не теряется при забывании отдельных путей.
Jump Game II: минимум прыжков как расширение по уровням
Тот же массив, более сложный вопрос: считая что конец достижим, какое наименьшее число прыжков нужно чтобы туда добраться? Думай об этом как о поиске в ширину по индексам. С 0 прыжков ты можешь быть только в индексе 0. С 1 прыжком ты можешь быть где угодно в [1 .. nums[0]]. С 2 прыжками — где угодно достижимом из всего этого первого диапазона. Каждое число прыжков задаёт непрерывный уровень: полосу индексов достижимых ровно этим числом прыжков.
Ты расширяешь уровень за уровнем. Держи три числа:
jumps— прыжки потраченные до сих пор.curEnd— правый край текущего уровня (самое дальнее где ты можешь быть сjumpsпрыжками).farthest— самое дальнее куда ты можешь добраться прыгнув с любого индекса внутри текущего уровня.
Проходи i слева направо (только до n - 2; ты не прыгаешь с цели). На каждом i продвигай farthest. Когда i достигает curEnd, ты прошёл весь текущий уровень, так что должен потратить один прыжок чтобы двинуться дальше: увеличь jumps и установи curEnd = farthest (правый край следующего уровня это всё что текущий уровень мог достичь). Это в точности BFS, но вместо очереди ты едешь по непрерывному фронтиру — поэтому это O(n), а не O(n) с накладными расходами очереди.
Gas Station: суммарное топливо, потом самокорректирующийся старт
Круговой маршрут из n заправок. Заправка i даёт gas[i] топлива; проезд от i до i+1 стоит cost[i]. Начни с пустым баком на какой-то заправке, проедь полный круг по часовой стрелке, верни стартовый индекс если маршрут возможен, иначе -1. Бак никогда не должен уходить в минус.
Два жадных факта решают её за один проход:
- Выполнимость = сумма. Сложи чистый
gas[i] - cost[i]по всем заправкам. Еслиtotal < 0, ты сжигаешь больше чем везёшь откуда бы ни стартовал — верни-1. Еслиtotal >= 0, верный старт гарантированно существует. Весь вопрос выполнимости сводится к одной сумме. - Найди старт сбросом. Пройди один раз, держа текущий
tank(чистое топливо с момента кандидата на старт) и индексstart. Прибавляй чистое значение каждой заправки кtank. В тот миг когдаtank < 0, кандидатstartне может сработать — и, что важно, не может и любая заправка междуstartиi. Так что перепрыгни кандидата наi + 1и сбросьtank = 0. Продолжай. Когдаtotal >= 0, какой быstartни остался у тебя в конце, это верный ответ.
Глубокий момент это безопасность сброса, доказанная во вставках ниже: если ты иссяк двигаясь от start к i, ни одна заправка на этом отрезке тоже не является жизнеспособным стартом, так что ты ничего не теряешь пропустив их все разом. Именно это делает один проход достаточным.
Jump Game: можешь ли ты добраться до последнего индекса?
Состояние это одно число, farthest. Цикл делает проверку достижимости, потом продвигает фронтир.
1
function canJump(nums) {
2
let farthest = 0; // best index reachable so far
3
for (let i = 0; i < nums.length; i++) {
4
if (i > farthest) { // i is beyond the frontier
5
return false; // unreachable: stranded
6
}
7
farthest = Math.max(farthest, i + nums[i]); // extend the frontier from i
8
}
9
return true; // never got stranded
10
}
- L2 Всё состояние это одно число: самый дальний индекс достижимый из всего увиденного до сих пор. Начинается с 0 (мы начинаем стоя на индексе 0).
- L4 Проверка достижимости СНАЧАЛА. Если текущий индекс ускользнул за фронтир, никакой более ранний индекс не мог запустить нас сюда -> разрыв который мы не можем пересечь.
- L5 Верни false в тот миг когда мы застряли. Ни один путь не изучен, без возвратов.
- L7 i достижим, так что с i мы можем прыгнуть на i + nums[i]. Держи максимум: фронтир только и делает что движется вперёд.
- L9 Завершили проход ни разу не провалив проверку -> последний индекс был достижим.
Jump Game II: минимум прыжков через расширение по уровням
Та же идея самого дальнего охвата, плюс ещё два числа чтобы считать BFS-уровни.
1
function jump(nums) {
2
let jumps = 0; // jumps spent so far
3
let curEnd = 0; // right edge of current level
4
let farthest = 0; // best reach from this level
5
for (let i = 0; i < nums.length - 1; i++) { // stop before the goal index
6
farthest = Math.max(farthest, i + nums[i]); // extend reach within level
7
if (i === curEnd) { // consumed the whole level
8
jumps++; // one jump buys the next level
9
curEnd = farthest; // its edge = everything reachable
10
}
11
}
12
return jumps;
13
}
- L5 Цикл только до n-2: ты никогда не прыгаешь С последнего индекса, ты прибываешь на него. Цикл до конца переcчитал бы один прыжок лишний раз.
- L6 Пока внутри текущего уровня, продолжай продвигать самый дальний индекс которого может достичь любой его член.
- L7 Достижение curEnd значит что мы прошли весь текущий уровень. Чтобы продвинуться мы должны потратить прыжок.
- L8 Потрать прыжок.
- L9 Правый край следующего уровня это лучший охват который мы накопили -> зафиксируй фронтир как новый уровень.
Запуск обеих на одних и тех же массивах
canJump возвращает булево; jump возвращает минимальное число прыжков (для входов про которые известно что они достижимы).
[3,2,1,0,4] проваливается потому что 0 на индексе 3 это ловушка: лучший фронтир достигает индекса 3 но никогда индекса 4. Для [2,3,1,1,4] минимум это 2 прыжка (0 -> 1 -> 4): жадность которая всегда фиксируется на самом дальнем достижимом уровне доказуемо оптимальна.
Gas Station: выполнимость плюс сбрасывающийся старт
Один проход отслеживает глобальный total (выполнимость) и локальный tank + start (кандидата). Сброс это весь трюк.
1
function canCompleteCircuit(gas, cost) {
2
let total = 0; // net gas around the whole loop
3
let tank = 0; // running fuel since the candidate start
4
let start = 0; // current candidate starting station
5
for (let i = 0; i < gas.length; i++) {
6
const diff = gas[i] - cost[i]; // net fuel at station i
7
total += diff;
8
tank += diff;
9
if (tank < 0) { // ran dry before leaving i
10
start = i + 1; // none of start..i can begin the loop
11
tank = 0; // restart accounting from i+1
12
}
13
}
14
return total >= 0 ? start : -1; // feasible iff total net >= 0
15
}
- L2 Глобальный аккумулятор: чистое топливо по всему кругу. Один его знак решает существует ли ХОТЬ КАКОЕ-ТО решение.
- L3 Локальный аккумулятор: топливо собранное с момента текущего кандидата на старт. Именно это говорит нам выживает ли кандидат.
- L6 Чистое значение на этой заправке: данный газ минус стоимость проезда до следующей заправки. Может быть отрицательным.
- L9 Бак ушёл в минус -> мы не можем добраться до заправки i+1 с текущего старта.
- L10 Сдвинь кандидата за i. Ключевое утверждение (доказано во вставках): ни одна заправка на start..i тоже не может быть верным стартом, так что пропусти их все.
- L11 Свежий бак: учёт начинается заново с нового кандидата i+1.
- L14 Если чистая сумма неотрицательна решение существует, и выживший start верен; иначе ни один старт не работает.
У круга A чистая сумма (1-3)+(2-4)+(3-5)+(4-1)+(5-2) = -2-2-2+3+3 = 0 >= 0, так что старт существует; логика сброса приземляется на индекс 3. У круга B чистая сумма -1 < 0, так что ни один старт не работает и мы возвращаем -1. Единственный жизнеспособный старт круга C это индекс 4.
Давай пройдём по проходу Jump Game на [2, 3, 1, 1, 4] и посмотрим как единственное число farthest подытоживает каждый путь. Каждый кадр показывает текущий индекс i, проходит ли проверка достижимости (i <= farthest), и обновлённый фронтир.
1
function canJump(nums) {
2
let farthest = 0;
3
for (let i = 0; i < nums.length; i++) {
4
if (i > farthest) return false;
5
farthest = Math.max(farthest, i + nums[i]);
6
}
7
return true;
8
}
Заметь что фронтир farthest монотонно неубывающий: 0, 2, 4, 4, 4, 8. Проверка i > farthest ни разу не сработала, так что последний индекс достижим. Сравни [3,2,1,0,4]: фронтир застрял бы на 3 (0 на индексе 3 ничего не добавляет), и на i=4 проверка 4 > 3 сработала бы return false.
Время: O(n) для всех трёх
Каждый алгоритм здесь это один проход слева направо с O(1) работой на индекс — сравнение, сложение, max. Без вложенных циклов, без возвратов, без перечисления путей.
pass work per index total time extra space
Jump Game 1 O(1) O(n) O(1)
Jump Game II 1 O(1) O(n) O(1)
Gas Station 1 O(1) O(n) O(1)Для Jump Game альтернатива полным перебором (перепробовать каждый выбор прыжка) экспоненциальна; сворачивание множества путей в единственное число farthest это то что покупает линейное время. Для Jump Game II та же идея расширения по уровням могла бы быть закодирована как BFS с очередью — всё ещё O(n) работы но с выделением очереди и накладными расходами; езда по непрерывному фронтиру с тремя целыми убирает эту стоимость константного множителя. Для Gas Station наивный подход пробует каждую из n заправок как старт и симулирует полный круг — O(n^2); однопроходный сброс доказывает что тебе нужен только один проход.
Память: O(1) для всех трёх
Каждый алгоритм держит фиксированную горстку целых независимо от размера входа: farthest для Jump Game; jumps, curEnd, farthest для Jump Game II; total, tank, start для Gas Station. Без вспомогательного массива, без стека рекурсии. Это подпись чистой жадности: константное количество текущего состояния которое подытоживает всё что тебе нужно знать.
Жадная линза. Все три заменяют поиск по многим возможностям единственной локальной величиной которая доказуемо схватывает оптимум: самый дальний достижимый индекс, край текущего BFS-уровня, текущий бак с момента последнего сброса. Найти эту одну величину — и доказать что её достаточно — это всё искусство жадного проектирования.
В Jump Game (прыжках), какую единственную величину отслеживает жадный проход, и что она значит?
В Jump Game, когда ты заключаешь что последний индекс НЕ достижим?
В Jump Game II, почему цикл идёт только до индекса n-2 вместо n-1?
В Gas Station (заправках), какое единственное условие решает существует ли ХОТЬ КАКОЙ-ТО верный старт?
В Gas Station, что происходит в тот миг когда текущий бак уходит в минус на заправке i?
Почему сброс кандидата на старт на i+1 (а не start+1) безопасен в Gas Station?
Запусти проход самого дальнего охвата на [1, 0, 2]. После обработки индекса 0, farthest = 1. На индексе 1 (значение 0), farthest остаётся 1. Какой i на шаге где проверка достижимости i > farthest впервые проваливается? (Введи этот индекс.)
Почему это работает
Почему total >= 0 гарантирует старт в Gas Station. Предположим total >= 0. Запусти алгоритм; он заканчивает держа какого-то кандидата start. Каждый сброс случился потому что бак ушёл в минус до достижения start, так что отрезок от start до конца массива ни разу не опустился ниже нуля. А что насчёт обёртки от конца обратно к start? Топливо использованное там равно total минус (неотрицательное) топливо накопленное на отрезке start..end. Поскольку total >= 0, эта часть с обёрткой тоже не может толкнуть бак ниже нуля. Так что полный круг начинающийся с start всегда держит бак >= 0. Глобальная сумма будучи неотрицательной поэтому не только необходима но и достаточна.
Частая ошибка
Ошибка: возврат -1 слишком рано, или проверка не того условия. Частый баг в Gas Station это возврат -1 в первый раз когда локальный tank уходит в минус. Это неверно: отрицательный бак лишь делает недействительным текущего кандидата, не всю задачу — ты должен продолжать проход, сбрасывая старт, и решить выполнимость из глобального total в конце. Зеркальная ошибка в Jump Game это проверка nums[i] === 0 чтобы обнаружить провал. 0 безвреден если он не сидит ровно на фронтире и ничто не достаёт дальше. Правильный, достаточный тест провала чисто позиционный: i > farthest.
Граничные случаи
Случаи с одним элементом и ловушкой. Jump Game на [0]: цикл выполняется раз на i=0, проверка 0 > 0 ложна (ты уже на последнем индексе), и он возвращает true — массив длины 1 тривиально решён без прыжков. Jump Game II на [0] возвращает 0 потому что тело цикла (которое идёт до n-2 = -1) ни разу не выполняется: ноль прыжков нужно. Классическая ловушка это 0 достижимый но блокирующий: [3,2,1,0,4]. Фронтир взбирается до 3 но 0 на индексе 3 ничего не продвигает, так что на i=4 проверка 4 > 3 срабатывает и он верно возвращает false. Всегда проверяй массив у которого единственный ноль сидит ровно на фронтире.
Ещё практика
Жадный рецепт который обе задачи разделяют. (1) Определи полный перебор (перечисли все пути / перепробуй каждый старт) и его плохую сложность. (2) Спроси: есть ли единственная локальная величина которая подытоживает всё что мне нужно, делая поиск ненужным? Jump Game -> самый дальний достижимый индекс. Gas Station -> текущий бак плюс глобальная сумма. (3) Определи правило обновления и тест решения на этой величине. (4) Докажи что локальный выбор никогда не теряет оптимум (монотонный фронтир; безопасный сброс). (5) Подтверди что одного O(1)-на-шаг прохода достаточно, давая O(n). Когда ты можешь назвать величину и обосновать почему её достаточно, у тебя есть жадное решение.
Объясни жадное озарение за Jump Game и Gas Station: какую локальную величину отслеживает каждая, тест решения, почему сброс в Gas Station безопасен, условие выполнимости, и сложность.
Две знаменитые жадные задачи, обе решены отслеживанием единственной локальной величины за один O(n) проход.
Jump Game — самый дальний достижимый индекс. Неси farthest, наибольший индекс достижимый до сих пор. Проходи i слева направо: если i > farthest ты застрял (верни false); иначе продвинь farthest = max(farthest, i + nums[i]). Заверши проход и последний индекс достижим. Одно число заменяет перебор каждого пути потому что достижимость монотонна — нет дыр позади фронтира.
Jump Game II — минимум прыжков как расширение по уровням. Трактуй числа прыжков как непрерывные BFS-уровни. Держи jumps, curEnd (край текущего уровня), farthest (лучший охват с этого уровня). Иди циклом только до n-2; когда i достигает curEnd, потрать прыжок и установи curEnd = farthest. Оптимально и O(n) с тремя целыми, без очереди.
Gas Station — суммарное топливо, потом самокорректирующийся старт.
- Выполнимость: круговой маршрут возможен тогда и только тогда, когда суммарное чистое топливо
sum(gas[i] - cost[i]) >= 0. Весь вопрос сводится к одной сумме. - Найди старт: пройди один раз с текущим
tankи кандидатомstart. Всякий раз когдаtank < 0, сбросьstart = i + 1иtank = 0. Выжившийstartверен когдаtotal >= 0. - Почему сброс безопасен: иссякание от
startдоiдисквалифицирует каждую заправку на этом отрезке как старт, так что пропуск их всех ничего не теряет.
Сложность: все три это O(n) время и O(1) память — фиксированная горстка целых, один проход, без рекурсии. Жадное искусство это нахождение локальной величины которая доказуемо схватывает оптимум (самый дальний охват, край уровня, текущий бак) и доказательство что локальный выбор никогда не теряет.
Это закрывает раздел жадности: ты видел аргумент обмена, планирование интервалов, и теперь две задачи-завсегдатая жадности. Следующий раздел переходит к новому алгоритмическому шаблону.