Круговой маршрут по заправкам
Medium
Круговой маршрут по станциям: на i получаете
gas[i] топлива и тратите cost[i], чтобы доехать до следующей. Верните индекс единственной стартовой станции, с которой можно проехать полный круг без отрицательного бака; если такого старта нет — -1.Примеры:
Вход:
{"gas": [1, 2, 3, 4, 5], "cost": [3, 4, 5, 1, 2]}
Выход:
3
Объяснение: Старт с индекса 3 (gas 4, cost 1): дальше хватает топлива на весь круг → 3.
Вход:
{"gas": [2, 3, 4], "cost": [3, 4, 3]}
Выход:
-1
Объяснение: Суммарно gas 2+3+4=9 меньше cost 3+4+3=10, полного круга ниоткуда не выйдет → -1.
Вход:
{"gas": [5], "cost": [4]}
Выход:
0
Объяснение: Одна станция: 5≥4, круг из одного ребра успешен → старт 0.
Ограничения:
1 <= gas.length = cost.length <= 10^5
Ответ существует не более чем в одном экземпляре
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!