134. Gas Station

https://leetcode-cn.com/problems/gas-station/

image.png

（图片来源https://leetcode-cn.com/problems/gas-station/

）

日期	是否一次通过	comment
2020-03-17	0

---

// 总量上，gas >= cost，才会存在解
    // 有解的情况下，油多的点多出来的油 能够供给油少的点，否则该点不是起点；最终状态是所有点都能够连接起来
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int currDiff = 0, currSum = 0, totalDiff = 0;
        int idx = 0;

        for(int i = 0; i < gas.length; i++) {
            currDiff = gas[i] - cost[i];
            currSum += currDiff;
            totalDiff += currDiff;  // 记录 sum(gas-cost)

            if(currSum < 0) {  // 入不敷出，下一节点作为起始点
                currSum = 0;
                idx = i + 1;
            }
        }

        return  totalDiff >= 0 ? idx : -1;
    }