134. Gas Station
在一條環形路線上有 n 個加油站，其中第 i 個加油站有 gas[i] 單位的汽油。
你有一輛無限油箱的車，但從第 i 個加油站到下一個 (i + 1) 個加油站需要 cost[i] 單位的汽油。你從其中一個加油站開始旅程，並且油箱是空的。
給定兩個整數數組 gas 和 cost，如果你能夠順時針繞環形路線行駛一圈，返回起始加油站的索引，否則返回 -1。如果存在解，保證該解是唯一的。
範例：
輸入：gas = [1,2,3,4,5], cost = [3,4,5,1,2] 輸出：3 解釋： 從加油站 3（索引 3）開始，加滿 4 單位的汽油。你的油箱 = 0 + 4 = 4 行駛到加油站 4。你的油箱 = 4 - 1 + 5 = 8 行駛到加油站 0。你的油箱 = 8 - 2 + 1 = 7 行駛到加油站 1。你的油箱 = 7 - 3 + 2 = 6 行駛到加油站 2。你的油箱 = 6 - 4 + 3 = 5 行駛到加油站 3。消耗的油量為 5。你的汽油剛好足夠返回到加油站 3。 因此，返回 3 作為起始索引。
Python
from typing import List
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
total_gas, total_cost, current_gas = 0, 0, 0
start_index = 0
for i in range(len(gas)):
total_gas += gas[i]
total_cost += cost[i]
current_gas += gas[i] - cost[i]
# If current_gas drops below 0, reset start index to the next station
if current_gas < 0:
start_index = i + 1
current_gas = 0
# If total gas is less than total cost, it's impossible to complete the circuit
if total_gas < total_cost:
return -1
return start_index
22.03MB, 944ms
C++
#include <vector>
using namespace std;
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total_gas = 0, total_cost = 0, current_gas = 0;
int start_index = 0;
for (int i = 0; i < gas.size(); ++i) {
total_gas += gas[i];
total_cost += cost[i];
current_gas += gas[i] - cost[i];
// If current_gas drops below 0, reset start index to the next station
if (current_gas < 0) {
start_index = i + 1;
current_gas = 0;
}
}
// If total gas is less than total cost, it's impossible to complete the circuit
if (total_gas < total_cost) {
return -1;
}
return start_index;
}
};
130.44MB, 99ms
Javascript
/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
var canCompleteCircuit = function(gas, cost) {
let totalGas = 0, totalCost = 0, currentGas = 0;
let startIndex = 0;
for (let i = 0; i < gas.length; i++) {
totalGas += gas[i];
totalCost += cost[i];
currentGas += gas[i] - cost[i];
// If currentGas drops below 0, reset startIndex to the next station
if (currentGas < 0) {
startIndex = i + 1;
currentGas = 0;
}
}
// If total gas is less than total cost, it's impossible to complete the circuit
if (totalGas < totalCost) {
return -1;
}
return startIndex;
};
61.08MB, 76ms
