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 in the clockwise direction, otherwise return -1.

Note:

• If there exists a solution, it is guaranteed to be unique.
• Both input arrays are non-empty and have the same length.
• Each element in the input arrays is a non-negative integer.

Example 1:

Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: 
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

---

给定一个圆环，环上有n个加油站，每个加油站有gas[i]升油，一辆车从第i个加油站走到第i+1个加油站需要耗费cost[i]升油。问该车能否绕行圆环一周，如果能给出起点。

1. 对于某个点i，如果gas[i]-cost[i]>=0，则车能从i走到i+1。
2. 如果从A出发，无法到达B（但能到达B-1），则所有在A、B之间的起点都无法到达B。反证法，想象一下，如果A,B之间有一起点C能到达B，则说明C到B之间总的gas大于中的cost，又因为C在A,B之间，A能到达C，说明A到C之间中的gas大于cost。那么，既然A能到C，C能到B，则A能到B，和前提假设矛盾，所以原命题成立。
3. 如果圆环上中的gas大于总的cost，则一定有一个解。
4. 假设解的起点为i，则从i肯定能到达环上的任意一点。

基于以上的讨论，本题的解法是这样的：

1. 从0开始走，如果能到达i，但无法到达i+1，则所有0~i的点都不是起点，因为根据讨论2，0~i的点都无法到达i+1，而根据讨论4，0~i的点不可能是解。
2. 所以尝试起点为i+1，继续往前走。
3. 最后，如果满足3，因为其他所有点都不可能是正确答案，且根据题目，解是唯一的，所以上述过程找到的起点就是正确解。

完整代码如下：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        int gasSum = 0, costSum = 0, tank = 0, start = 0;
        for (int i = 0; i < gas.size(); ++i) {
            gasSum += gas[i];
            costSum += cost[i];
            tank += (gas[i] – cost[i]);
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        if (gasSum < costSum)
            return -1;
        else
            return start;
    }
};

本代码提交AC，用时6MS。