134.加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

解题思路

模拟：枚举遍历每次满足条件的候选者。

代码

class Solution {

    public int canCompleteCircuit(int[] gas, int[] cost) {

        //模拟

        int n = gas.length,sum = 0,index = 0,tsum = 0;

        for(int i = 0;i < n; i++) {

            tsum += gas[i]-cost[i];//纪录总剩余油

            sum += gas[i]-cost[i]; //记录index候选者当前总剩余油

            if(index == -1 && sum > 0 && gas[i] > cost[i]) index = i;//找到候选者

            else if(sum < 0){

                index = -1;

                sum = 0;

            }

        }

        if(tsum < 0) return -1;//总油小于0不可能绕一周

        return index;

    }

}