描述

在一个环形的线路上有N个加油站，第i个加油站的储量为gas[i]。假设有一辆油箱无限大的汽车，从第i个加油站行驶到第i+1个加油站需要消耗cost[i]汽油，是否能从一个加油站出发，一次性的走完所有的加油站。

分析

依次遍历，在经过一个加油站时把油站的储量全部装入到油箱，则从第i个站点出发，则行驶到第i+1个站点后：

油箱剩余油量：sum += (gas[i] - cost[i]);

1, sum < 0，说明从第i个节点及之前的节点出发，不可以完成一次环行；如果存在可以完成环行的节点也在第i个节点之后了；

2，sum >= 0，说明可可以从i行驶到第i+1个节点;

整个环路上行驶剩余的油量为：total += (gas[i] - cost[i])

1，total < 0，说明油站节点储存总量小于消耗量，不能完成环形行驶；

2，total >= 0，说明存在完成环形行驶的解；

实现

int gasStation(vector<int> &gas, vector<int> &cost) {
    int total = 0;
    int j = -1;
    for (int i = 0, sum = 0; i < gas.size(); ++i) {
        sum += gas[i] - cost[i];
        total += gas[i] - cost[i];
        if (sum < 0) {
            j = i;
            sum = 0;
        }
    }
    return total >= 0 ? j + 1 : -1;
}