【LeetCode】134.Gas Station

Problem:

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.

Solution:

车在 i 站开往 i+1 站，有两种可能：一是车在 i 站加油后所剩油量足够其到达 i+1 站，二则是不足使其到达。

-----------station i-----------------------------------------------station i+1--------

...  pos[i] + gas[i]                     -cost[i]              =pos[i+1] + gas[i+1]  ...

当车从 0 站开往 i+1 站后，剩余油量pos<0，说明当起始站为 0 站，车无法抵达 i+1 站。

得到这一结论后，又可以推出当车从0~i+1之间任何一个站点出发都无法抵达 i+1 站——既然在 i+1 站之前的任何一个站点都有 pos>=0（总油量一直在增加）仍然无法使车到达 i+1，那么在0~i间任何一个站点出发 pos 必然小于等于从 0 出发时的 pos，即更不可能到达 i+1 站。

如此当start∈[0，i]，车无法走完全程。探索下一步就要从 i+1 站开始了，按原来方法继续遍历，直到计数 i 不再满足 i<gasSize，就可以返回最终结果了。

Code:

//in C language

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    int start=0;//starting station‘s index
    int pos=0;//gas‘s positive accumulation
    int neg=0;//gas‘s negative accumulation
    
    for(int i=0;i<gasSize;i++){
        pos+=gas[i]-cost[i];
        if(pos<0){
            neg+=pos;
            start=i+1;//starts from 0 to i are all impossible.
            pos=0;
        }
    }

    if(pos+neg>=0)
        return start;
    else
        return -1;
}

最后判断是否能走完全程的if-else语句的解释——最终的neg表示之前所有尝试失败情况下离到达下一站所欠油量的总和，最终的 pos 则是最后一次尝试直到回到最开始的 0 站后所剩的油量。如果这时满足 pos+neg>=0，则从最后一次尝试的起点出发，必然能完整走上一圈，反之则不能。

【LeetCode】134.Gas Station

原文：http://www.cnblogs.com/liez/p/5300034.html