Код Senior Жадные обновлено
Круговой маршрут
Условие
На станциях есть gas[i] топлива, переезд до следующей стоит cost[i]. С какой станции можно объехать круг? Решение единственно, иначе -1.
Примеры
canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) // 3
canCompleteCircuit([2, 3, 4], [3, 4, 3]) // -1
canCompleteCircuit([5], [4]) // 0
Как подойти
Два независимых наблюдения дают решение за один проход. Первое отвечает на существование, второе - на позицию: при уходе бака в минус весь пройденный отрезок отпадает целиком, потому что любой его префикс ещё хуже. Перебор всех стартов дал бы O(n²).
Подсказки: 2
- Если суммарного топлива меньше суммарной стоимости, ответа нет вовсе.
- Если бак ушёл в минус на участке, ни одна станция этого участка стартом быть не может.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.