暴力思路

1. 直觉上感到一定第i个点的cost>gas时可以作为起点.
2. 遍历第一个可能的起点, 验证其是否能再次到达该起点.
3. 这是暴力的想法.

优化

1. 这题并不需要为每一个可能的起点遍历其是否能重新回到起点, 而只需要在宏观上验证油量能否保证绕一圈. $\Sigma{0,N} gas_i-cost_i$
2. 起点的确定方式比较简单, 任何一个gas[i] > cost[i]的i处都可以作为起点.

代码

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total_need = 0, cur_profit = 0, start = 0;
        for(int i = 0; i < gas.length; i++){
            total_need += gas[i] - cost[i];
            cur_profit += gas[i] - cost[i];
            if(cur_profit < 0){
                start = i+1;
                cur_profit = 0;
            }
        }
        return total_need >= 0 ? start : -1;
    }
}