LeetCode: 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, otherwise return -1.

Note:
The solution is guaranteed to be unique.

地址：https://oj.leetcode.com/problems/gas-station/

算法：一个简单粗暴的方法是，从第0个station开始试，看其是否可以绕一圈回到起点，这样的时间复杂度是$\O(n^2)$，如果用这种方法那么肯定是会超时的（当时我也是用这个方法，下面这个巧妙的方法也是参考了网上的答案）。那么，下面我们介绍一种线性时间复杂度的算法，这个算法是对上面一种方法的改进。这个方法最核心的思想是基于如下的事实：假如从第0个station可以到达第$j=1,2,\cdots,i-1$个station，但无法到达第i个station的话，那么从第$j=1,2,\cdots,i-1$个station出发也肯定无法到达第i个station。原因很简单，假如可以从第j个station到达第i个station，那么我们可以先从第0个到达第j个，然后在从第j个到达第i个，也就是说我们可以从第0个到达第i个，故这个假设是不成立的。这样的话，当我们判断从第0个station无法到达第i个时，可以不用回过头从第1个station判断，我们可以直接继续从第i+1个station开始判断。由于题目说至少会存在一个解，也就是我们不需要去判断不存在解的情况，所以只要循环一遍就足够了。代码：

 1 class Solution { 2 public: 3     int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { 4         int n = gas.size(); 5         int sum_gas = 0, sum_cost = 0; 6         for(int i = 0; i != n; ++i){ 7             sum_gas += gas[i]; 8             sum_cost += cost[i]; 9         }10        if (sum_cost > sum_gas){11            return -1;12        }13        sum_gas = 0;14        sum_cost = 0;15        int start = 0;16        for(int i = 0; i != n; ++i){17            sum_gas += gas[i];18            sum_cost += cost[i];19            if(sum_gas >= sum_cost){20                continue;21            }else{22                start = (i + 1) % n;23                sum_gas = 0;24                sum_cost = 0;25            }26        }27        return start;28     }29 };

LeetCode: Gas Station