题目：
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.链接：
题解：
经典题gas station，贪婪法。设计一个局部当前的gas，一个全局的gas，当局部gas小于0时，局部gas置零，设置结果为当前index的下一个位置，此情况可能出现多次。当全局gas小于0的话说明没办法遍历所有gas站，返回-1。
Time Complexity - O(n)， Space Complexity - O(1)。
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { if(gas == null || cost == null || gas.length == 0 || cost.length == 0 || gas.length != cost.length) return 0; int curGas = 0; int totalGas = 0; int result = 0; for(int i = 0; i < gas.length; i++){ curGas += gas[i] - cost[i]; totalGas += gas[i] - cost[i]; if(curGas < 0){ result = i + 1; curGas = 0; } } if(totalGas < 0) return - 1; return result; }}
Update:
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { if(gas == null || cost == null || gas.length != cost.length || gas.length == 0) return -1; int len = gas.length; int totalGasRequired = 0, curGas = 0, station = 0; for(int i = 0; i < len; i++) { totalGasRequired += gas[i] - cost[i]; curGas += gas[i] - cost[i]; if(curGas < 0) { curGas = 0; station = i + 1; } } return totalGasRequired >= 0 ? station : -1; }}
二刷:
Java:
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { if (gas == null || cost == null || gas.length != cost.length) return -1; int totalCost = 0, totalGas = 0, curTank = 0, startingIndex = 0; for (int i = 0; i < gas.length; i++) { totalGas += gas[i]; totalCost += cost[i]; curTank += (gas[i] - cost[i]); if (curTank < 0) { curTank = 0; startingIndex = i + 1; } } return totalGas >= totalCost ? startingIndex : -1; }}
测试：