题目描述
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 in the clockwise direction, otherwise return -1.
Example1:
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.
Example2:
Input: gas = [2,3,4] cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.
NOTE
- If there exists a solution, it is guaranteed to be unique.
- Both input arrays are non-empty and have the same length.
- Each element in the input arrays is a non-negative integer.
解题思路
- 给你一堆加油站，和去每个加油站的消耗，要求找到从某个位置开始能够顺时针遍历一圈。
- 记录最后一个加起来小于零的索引，然后返回这个索引+1就是答案了。
- 从0开始以其为起点实验，累加 restGas += gas[i] - cost[i]
- 一旦在 i 处遇到restGas<0，那么就说明当前选择的起点beg不行，需要重新选择，此时我们不应该回去使用 beg+1 作为新起点，遍历到 size-1 处就可以结束了，如果找到了可能的起点，我们还要进行验证，走一遍(total)。
- 其实本质就是：这个起点将路径分为前后两段，前段总的余量为负，即油不够用
- 要想有解，那么后段油量应该为正，此时才可能有解，我们要做的就是找到这个分割点作为起点，然后再验证一下；
- 反之，如果前段就为正了，那么显然可以直接选择前面的点为起点；如果整段加起来都是负的，那么无解。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int sum = 0;
int rest = 0;
int start = 0;
for(int i = 0; i < gas.size(); i++){
rest += gas[i] - cost[i];
sum += gas[i] - cost[i];
if(sum < 0){
start = i + 1;
sum = 0;
}
}
return rest < 0 ? -1 : start;
}
};
