题目描述

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 个加油站，其中第i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第i+1个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

算法1

(暴力枚举) $O(n^2)$

题解1:很自然想到的$O(n^2)$的算法，枚举每一个加油站作为起点，判断从该起点开始能否换绕一圈。

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for(int i = 0 ; i < n ; i ++)
        {
            int amount = 0 ,k = 0;
            for(k = 0 ; k < n ; k ++)
            {
                amount += gas[(i + k) % n] - cost[(i + k) % n];
                if(amount < 0) break;
            }
            if(k == n) return i;
        }
        return -1;
    }

算法2

(优化) $O(n)$

题解2:我们几乎可以很确定的上述解法不可能是最优的，因为我们对每个经过每个加油站后的油量变化做了太多次重复计算。我们令$total = \sum \limits_{i = 0}^{n - 1}(gas[i] - cost[i])$，如果$total < 0$，那么显然是无法成功的，我们直接返回-1。如果$total >= 0$的话，我们至少可以找到一个点$N_s$使得我们能够从$N_s$开始环绕一周（正确性稍后证明），我们找的方式如下：使用cur代表当前油箱内有多少油，每次cur += gas[i] - cost[i]，当cur < 0的时候，说明我们无法从0开始走到i + 1，那么就让i + 1变成新的起点，同时让cur = 0。

问题其实可以转化为给一个数组A（每个元素都是gas[i] - cost[i]），已知数组中元素的和大于等于0（total > 0），那么一定可以找到一个位置$N_s$，使得我们从该位置开始循环叠加一圈，在每一步的累加和都大于等于0。

经过上述搜索，我们可以确保能够从$N_s$顺利的走到0，即$\sum \limits_{i = N_s}^{n - 1}A[i] \geq 0$，我们关心的是在这之后能否继续从0顺利的走到$N_s$呢，即$\sum \limits_{i = N_s}^{n - 1}A[i] +\sum \limits_{i = 0}^{k - 1} A[i] \geq 0 (0 < k \leq N_s)$？

我们使用反证法来证明这个问题，假设存在一个位置$0 < k <= N_s$，使得我们无法从$N_s$走回到$k$，这就意味着$\sum \limits_{i = N_s}^{n - 1}A[i] + \sum \limits_{i = 0}^{k - 1} < 0$。那么我们按照$k$和$N_s$将数组划分为3个部分，[0:k - 1],[k,N_s - 1],{N_s,n - 1}，因为$total > 0$，所以我们有：
$$\sum_{i=0}^{k - 1} \alpha_{i}+\sum_{i=k}^{N_{s}-1} \alpha_{i}+\sum_{i=N_{s}}^{n - 1} \alpha_{i} \geq 0$$
又因为$\sum \limits_{i = k}^{N_s -1}\alpha_i < 0$，这是最早可行的开始点前面肯定是连续若干个负数，不然的话我们就可以从更早的点开始出发并且顺利到达0点。所以可以得到
$$\sum_{i=0}^{i=k} \alpha_{i}+\sum_{i=N_{s}}^{i=N} \alpha_{i} \geq 0$$
这又是和我们的假设是矛盾的，所以上述做法是正确的。

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

此外这题的follow up 也很有意思，比如只能最多停k次？汽车油箱并不是无限的。