# 134. Gas Station

There are  N  gas stations along a circular route, where the amount of gas at station  i  is `gas[i]`.

You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from station  i  to its next station ( i +1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

``````class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total = 0, sum = 0, start = 0;
for (int i = 0; i < gas.size(); ++i) {
total += gas[i] - cost[i];
sum += gas[i] - cost[i];
if (sum < 0) {
start = i + 1;
sum = 0;
}
}
return (total < 0) ? -1 : start;
}
};
``````

``````class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total = 0, mx = -1, start = 0;
for (int i = gas.size() - 1; i >= 0; --i) {
total += gas[i] - cost[i];
if (total > mx) {
start = i;
mx = total;
}
}
return (total < 0) ? -1 : start;
}
};
``````

Reaching Points

Transform to Chessboard

Cheapest Flights Within K Stops

https://leetcode.com/problems/gas-station/discuss/42568/Share-some-of-my-ideas.

https://leetcode.com/problems/gas-station/discuss/42656/8ms-simple-O(n)-c++-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation