134.Gas Station

1-Greedy

https://leetcode.com/problems/gas-station/discuss/42568/

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sumCost = 0;
        int sumGas = 0;
        int tank = 0;
        int start = 0;
        for(int i = 0; i < gas.length; i++){
            sumGas += gas[i];
            sumCost += cost[i];
            tank += (gas[i] - cost[i]);
            //we have reached i, but after obtain gas[i], we can't reach i + 1;
            //So we must start from next station
            //Also the question guarantee only exist one valid solution
            if(tank < 0){
                start = i + 1;
                tank = 0;
            }
        }
        if(sumCost > sumGas)
            return -1;
        return start;
    }
}