面试经典 150 题 （十五）

画折线图，亏空最严重的一步要最后一步做，等着前面的增益补（总体收益大于等于0的情况），因为本题有解就唯一，当总gas大于总cost一定有解

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int spare = 0;
        int minSpare = Integer.MAX_VALUE;
        int minIndex = 0;

        for (int i = 0; i < len; i++) {
            spare += gas[i] - cost[i];
            if (spare <= minSpare) {
                minSpare = spare;
                minIndex = i;
            }
        }

        return spare < 0 ? -1 : (minIndex + 1) % len;
    }
}