134.md

Gas Station

题目

here 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.

思路

对于一个例子：
gas = [3,4,5,6,8],cost=[4,5,6,7,2]。

使用索引i遍历一边数组(两个数组同时)，如果gas[i]<cost[i]，那么该位置是不能作为起始位置的。只有当gas[i]>=cost[i]时i才可以作为起始位置。

所以上述的区间[0,3]的站点都是不能作为起始位置的，但是遍历的过程中有些信息是可以得到的，就是走过i站点到i+1站点需要的额外油量是可以知道
的，比如i=0的时候，走过0站点到1站点需要额外的油量|gas[0]-cost[0]| = 1，而1站点到2站点所需的额外油量也为1,2到3，3到4同理，即使用一个
request_gas的变量表示走过前边的站点所需要的总油量(request_gas=4)。最后在4站点可以作为起始位置，用start保留起始位置为i，并且多出油量
tank=gas[4]-cost[4]=8-2=6。

最后如果tank > request_gas表示start的位置开始可以巡回走完,返回start，否则返回-1。

算法的优越性在于使用了一个request_gas去保留了前边所有不能巡回走完的站点所需要的额外油量。

代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int stations = gas.size();
        int tank = 0;
        int request_gas = 0;
        int begin = 0;    //记录起始站
        //i的意义为从i起始，走向i+1站
        for(int i=0;i<stations;++i){
            tank += gas[i]-cost[i];
            //表示start起始走不到i+1站
            if(tank<0){
                request_gas += tank;//从0走到当前的i+1站需要额外的油量
                begin = i+1;//保留新的起始位置
                tank = 0;//并更新油箱
            }
        }
        //有可能从某一站开始是可以走到数组表示中的最后一个站的，此时还有
        //油量剩余，所以得加上。
        request_gas += tank;
        return (request_gas>=0)? begin:-1;
        
    }
};

func canCompleteCircuit(gas []int, cost []int) int {
    tank, lack, begin := 0, 0, 0
    for i := 0; i < len(gas); i++ {
        tank += gas[i] - cost[i]
        if tank < 0 {
            lack += tank
            tank = 0
            begin = i + 1
        }
    }
    if tank + lack >= 0 {
        return begin
    }
    return -1
}