LeetCode——加油站

Q：环形路上有n个加油站，第i个加油站的汽油量是gas[i].
你有一辆车，车的油箱可以无限装汽油。从加油站i走到下一个加油站（i+1）花费的油量是cost[i]，你从一个加油站出发，刚开始的时候油箱里面没有汽油。
求从哪个加油站出发可以在环形路上走一圈。返回加油站的下标，如果没有答案的话返回-1。
注意：
答案保证唯一。
A：
假设从站点 i 出发，到达站点 k 之前，依然能保证油箱里油没见底儿，从k 出发后，见底儿了。那么就说明 diff[i] + diff[i+1] + ... + diff[k] < 0，而除掉diff[k]以外，从diff[i]开始的累加都是 >= 0的。也就是说diff[i] 也是 >= 0的，这个时候我们还有必要从站点 i + 1 尝试吗？仔细一想就知道：车要是从站点 i+1出发，到达站点k后，甚至还没到站点k，油箱就见底儿了，因为少加了站点 i 的油.

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas.length == 0 || cost.length == 0)
            return -1;
        int j;
        int start = -1;

        for (int i = gas.length - 1; i >= 0; i--) {
            int remain = 0;
            j = i;
            while (true) {
                remain += (gas[j] - cost[j]);
                if (remain < 0)
                    break;
                if (j == i - 1 || (i == 0 && j == gas.length - 1)) {
                    start = i;
                    break;
                }
                j++;
                if (j >= gas.length)
                    j = 0;
            }
            if (start != -1)
                break;
        }
        return start;
    }