134. Gas Station

description

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.

题解

这道题是Medium难度，但是我看完题目后觉得很简单，显然是一道降低时间复杂度的问题，我是想不出来的，也懒的想了，随手写了个O(n^2)的算法，竟然通过了
具体的：将两个数组相减，结果如果大于0，说明此处可以作为起点，然后遍历这些点即可

public int canCompleteCircuit(int[] gas, int[] cost) {
    int res[]=new int[gas.length];
    for(int i=0;i<gas.length;i++){
        res[i]=gas[i]-cost[i];
    }
    for(int i=0;i<gas.length;i++){
        if(res[i]>=0&&isTravel(i,res))return i;
    }
    return -1;
}
private boolean isTravel(int i, int[] res) {
    int temp=i;
    int sum=0;
    for(;i<res.length;i++){
        sum+=res[i];
        if(sum<0)return false;
    }
    for(i=0;i<temp;i++){
        sum+=res[i];
        if(sum<0)return false;
    }
    return true;
}

当然要看看leetcode上的discuss了，下面这个解法是点赞最高的，给出的解释非常到位，如下：
I have thought for a long time and got two ideas:

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.)
If the total number of gas is bigger than the total number of cost. There must be a solution.
(Should I prove them?)

参考：https://discuss.leetcode.com/topic/1344/share-some-of-my-ideas
即如果A不能到B，那么A和B之间的点都不能到B，那么这些点都不用考虑，唯一解一定在后面的点，将start指向后面一个点，total记录整个差值的和 $\sum_{i}^{n}{(gas[i]-cost[i])}$ ，最后的结果中如果total小于0，说明无解，大于0，说明有解；根据前面的条件，如果有解，那么一定是start指向的点，这里留下一个问题：为什么total小于0就无解，大于0就有解？供思考…

public int canCompleteCircuit(int[] gas, int[] cost){
    int start,total,tank;
    start=total=tank=0;
    for(int i=0;i<gas.length;i++){
        if((tank+=gas[i]-cost[i])<0){
            start=i+1;
            total+=tank;
            tank=0;
        }
    }
    return total+tank>0?-1:start;
}