Сложность: medium
Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i].
У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций.
Учитывая два массива целых чисел gas и cost, верните индекс начальной заправочной станции, если вы можете проехать вокруг цепи один раз по часовой стрелке, в противном случае верните -1. Если решение существует, оно гарантированно будет уникальным.
Пример:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
👨💻 Алгоритм:
1⃣Инициализируйте переменные curr_gain, total_gain и answer значением 0.
2⃣Пройдите по массивам gas и cost. Для каждого индекса i увеличивайте total_gain и curr_gain на gas[i] - cost[i].
Если curr_gain меньше 0, проверьте, может ли станция i + 1 быть начальной станцией: установите answer как i + 1, сбросьте curr_gain до 0 и повторите шаг 2.
3⃣По завершении итерации, если total_gain меньше 0, верните -1. В противном случае верните answer.
😎 Решение:
function canCompleteCircuit($gas, $cost) {
$currGain = 0;
$totalGain = 0;
$answer = 0;
for ($i = 0; $i < count($gas); ++$i) {
$totalGain += $gas[$i] - $cost[$i];
$currGain += $gas[$i] - $cost[$i];
if ($currGain < 0) {
$answer = $i + 1;
$currGain = 0;
}
}
return $totalGain >= 0 ? $answer : -1;
}Ставь 👍 и забирай 📚 Базу знаний