Почему это работает
- Если машина от start осталась без бензина сразу после станции i, то ни одна станция между ними тоже не подходит: на i она приехала бы лишь с частью того же бензина, а каждый кусок до неё добавлял ≥ 0. Поэтому следующий старт — i + 1, и ни одна станция не проверяется дважды.
- Если total ≥ 0, бензина на круг хватает в сумме. Путь от последнего start до конца ни разу не уходит в минус, а оставшийся запас покрывает отрезок до start, который потерял ровно столько, сколько набрал остальной круг.
- Если total < 0, никакой старт не поможет: круг сжигает больше, чем даёт.
Сложность
Время O(n): один проход, каждая станция просматривается один раз. Память O(1): только total, tank и start. Перебор всех стартов занял бы O(n²).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗