Gas Station

Средняя№134сброс старта

На кольцевой дороге стоят заправки. Станция k даёт gas[k] единиц бензина, а дорога от неё до следующей стоит cost[k]. Машина стартует с какой-то станции с пустым баком. Найдите станцию, с которой можно проехать весь круг, или верните -1, если такой нет; если она есть, то одна. Наш пример: gas [4, 3, 1, 5, 2, 4, 1], cost [2, 2, 5, 2, 3, 2, 3] — ответ 3.

134 Gas StationРазбор · 1×

Пример: gas [4, 3, 1, 5, 2, 4, 1], cost [2, 2, 5, 2, 3, 2, 3]. gain — сколько станция добавляет в бак за вычетом своей дороги; tank — бензин при выезде с каждой станции на пути от start.

бензиндорогаgaintank04−2+213−2+121−5-435−2+342−3-154−2+261−3-2
ещё не дошлина пути от startстанция iне годится как стартответ

total — сумма по всем станциям: пока 0

01/41
сначала · назад · пуск · шаг
Скорость
1function canCompleteCircuit(gas, cost):
2 total = 0
3 tank = 0
4 start = 0
5 for i from 0 to len(gas) - 1:
6 gain = gas[i] - cost[i]
7 total = total + gain
8 tank = tank + gain
9 if tank < 0:
10 start = i + 1 // none of start..i works
11 tank = 0
12 return start if total >= 0 else -1
состояние
total
0
tank
–
start
–
i
–
gain
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Если машина от start осталась без бензина сразу после станции i, то ни одна станция между ними тоже не подходит: на i она приехала бы лишь с частью того же бензина, а каждый кусок до неё добавлял ≥ 0. Поэтому следующий старт — i + 1, и ни одна станция не проверяется дважды.
  2. Если total ≥ 0, бензина на круг хватает в сумме. Путь от последнего start до конца ни разу не уходит в минус, а оставшийся запас покрывает отрезок до start, который потерял ровно столько, сколько набрал остальной круг.
  3. Если total < 0, никакой старт не поможет: круг сжигает больше, чем даёт.

Сложность

Время O(n): один проход, каждая станция просматривается один раз. Память O(1): только total, tank и start. Перебор всех стартов занял бы O(n²).

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.