[LeetCode 134] Gas Station (Medi

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

• If there exists a solution, it is guaranteed to be unique.
• Both input arrays are non-empty and have the same length.
• Each element in the input arrays is a non-negative integer.

Example 1:

Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: 
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Solution: Greedy

1. 需要好好想一想。例如从站i出发，一旦发现某个站station j，diff 小于0时，那么根本不需要回到i + 1站去重新找，只需要从j + 1开始找。为什么？
2. 因为能够从i出发，能够走到j，最坏的情况下，中间这些站每一次都把油用光了，然后到了j加的油不够消耗的油了，那么从i ~ j中任何一个站出发，到了j都会遇到这个问题。
3. 那么好的情况呢？ 中间每一站都没有用光，还有剩余一直在累加，但到了 j，在此基础上又加了油还是不够消耗。 那么从i ~ j中任何一个站出发，累加的油只会更少，到了j还是会遇到这个问题。
4. 综上所述，没有必要从i ~ j中任何一站重新走一遍，直接到j + 1开始找即可。这样，走一遍即可找到结果

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0 || cost == null || cost.length == 0)
            return -1;
        
        int diff = 0;
        int total = 0;
        int circuitStart = 0;
        
        /*
         * 我们从0开始以其为起点实验，累加 restGas += gas[i] - cost[i]，一旦在 i 处遇到restGas<0，
         * 那么就说明当前选择的起点beg不行，需要重新选择，此时我们不应该回去使用 beg+1 作为新起点，
         * 因为在beg处，一定有 gas>=cost，说明 beg+1 到 i 处的总gas一定小于总的cost，
         * 选择其中任何一个作为起点还是不行的，所以应该跳过这些点，以 i+1 作为新起点，
         * 遍历到 size-1 处就可以结束了，如果找到了可能的起点，我们还要进行验证，走一遍(total)，
         * 如果没问题那么说明可以。

         * 其实本质就是：这个起点将路径分为前后两段，前段总的余量为负，
         * 即油不够用，要想有解，那么后段油量应该为正，此时才可能有解，
         * 我们要做的就是找到这个分割点作为起点，然后再验证一下；反之，
         * 如果前段就为正了，那么显然可以直接选择前面的点为起点；如果整段
         * 加起来都是负的，那么无解
         * 
         * */

        for (int i = 0; i < gas.length; i++) {
            diff += gas[i] - cost[i];
            total += gas[i] - cost[i];
            
            // once find the station where diff is < 0, then we find the sperate point 
            // where the first part the diff < 0, and the following part diff must > 0 if there is a station exists
            // we don't break the loop coz, we need to verify if there is no more diff < 0 until reach the end
            if (diff < 0) {
                circuitStart = i + 1;
                diff = 0;
            }
        }
        
        return total < 0 ? -1 : circuitStart;
    }
}