LeetCode 134 Gas Station

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, otherwise return -1.

Note:The solution is guaranteed to be unique.

典型的数学题，感觉就是要找规律然而又fail了。。。数学是有多差。。。

一开始brute force最终运算时间超时。。。

网上看了discuss后才找到数学规律。。。有点迷茫不知道该怎么提升这种解决数学问题的能力。。。

• If car starts at A and can not reach B. Any station between A and B
  can not reach B.(B is the first station that A can not reach.)

这是将O(n^2)复杂度变为O(N)的关键一步，原先的搜索判断每一个station是否可以成为start station。对于station[0...i...n]而言，若station i不能作为start， 则判断i+1是否可以作为start。

而根据上述observation，若station i无法达到station j，则station i与j之间的任何station，都无法到达station j！！！

因此，station i与j之间的任何station，都无法作为start station（因为它们连j都到不了，更别说绕足一圈了），下次搜索可以直接跳到station j！！！

参考下图：

gas station.png

在遍历到station i时，判断它是否能够达到后面的节点，发现i+1,i+2,i+3均可以到达，直到station j，net[j]<0因此i不能到达j。

下面重点来了，net[j]取决于从i开始net之和，由于前三个节点可以达到，对应的net都是大于0的！！！

因此，若以station i+1作为start，到station j的net[j]只会更小，所以必然小于0！！！

因此station i,i+1,i+2,i+3这三个station，都无法到达station j！！！

英文版证明：
Proof to the first point: say there is a point C between A and B -- that is A can reach C but cannot reach B. Since A cannot reach B, the gas collected between A and B is short of the cost. Starting from A, at the time when the car reaches C, it brings in gas >= 0, and the car still cannot reach B. Thus if the car just starts from C, it definitely cannot reach B.

• If the total number of gas is bigger than the total number of cost. There must be a solution.

这个也非常tricky！！！遍历所有station后，只要gas的总和大于cost的总和，则必然存在一个解！！！

why？我第一次看到的时候真是没啥头绪。。。

证明如下，用的类似数学归纳法，感谢discuss上的大神。。。

Proof for the second point:

• If there is only one gas station, it’s true.
• If there are two gas stations a and b, and gas(a) cannot afford cost(a), i.e., gas(a) < cost(a), then gas(b) must be greater than cost(b), i.e., gas(b) > cost(b), since gas(a) + gas(b) > cost(a) + cost(b); so there must be a way too.
• If there are three gas stations a, b, and c, where gas(a) < cost(a), i.e., we cannot travel from a to b directly, then:
• either if gas(b) < cost(b), i.e., we cannot travel from b to c directly, then gas(c) > cost(c), so we can start at c and travel to a; since gas(b) < cost(b), gas(c) + gas(a) must be greater than cost(c) + cost(a), so we can continue traveling from a to b.
• Key Point: this can be considered as there is one station at c’ with gas(c’) = gas(c) + gas(a) and the cost from c’ to b is cost(c’) = cost(c) + cost(a), and the problem reduces to a problem with two stations. This in turn becomes the problem with two stations above.
• or if gas(b) >= cost(b), we can travel from b to c directly. Similar to the case above, this problem can reduce to a problem with two stations b’ and a, where gas(b’) = gas(b) + gas(c) and cost(b’) = cost(b) + cost(c). Since gas(a) < cost(a), gas(b’) must be greater than cost(b’), so it’s solved too.
• For problems with more stations, we can reduce them in a similar way. In fact, as seen above for the example of three stations, the problem of two stations can also reduce to the initial problem with one station.

代码：

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        // total表示遍历一遍后，gas与cost的差值
        // tank表示经过station i后，到达station i+1时，油箱里剩余的燃油量
        // 在到达下一个station时，需满足tank>=k，否则不可能到达该station。
        int total = 0, tank = 0, index = 0; 
        for (int i = 0; i < n; i++) {
            tank += gas[i] - cost[i];
            total += tank;
            if (tank < 0) {
                tank = 0;
                index = i + 1;
            }
        }
        if (total < 0) return -1;
        else return index;
    }
}

参考：
https://discuss.leetcode.com/topic/1344/share-some-of-my-ideas