Gas Station

1.题目描述（难度Medium）

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.

2.题目分析

题目要求给定两个长度为N的列表 gas, cost,分别记录的是当前加油站有的油，和从当前顺序去下一个加油站需要消耗的油。假定我们初始的油箱为空且无限大，不会有溢出的问题。我们需要在列表[0,1,2,3,..,N]的位置里选一个位置出发，使得我们可以在这条线路上无限循环[start...N-1,0,1,...start...]。
那么能满足这个要求的，就是当下一站是出发点的时候，我们还有油。满足这一条件，我们就可以无限循环

解题思路：
因为初始剩余油量为0，所以选择一个start 作为出发点，循环一圈。
若[start...start-1]均满足:”当前加油站的gas[i]-到下一站的cost[i] + i-1站到i站的剩余油量 > 0 ，那么start即为我们要求的出发点。

3.解题过程

Begin（算法开始）
输入 长度为N的list：gas,cost
遍历start in（0，N-1）：
  cur_gas = gas[start]-cost[start]
  cur_index = (start +1)%N
  while cur_index!=start and cur_gas>=0://只要要去下一站的站不是起始站且当前有油
   cur= (cur+1)%N；cur_gas += gas[cur_index]-cost[cur_index]
  if cur_gas>=0:这里是判断是否回到最初地址的时候还有油
   return start

返回 -1
End （算法结束）

//这是个初始算法，在具体实施中，有很多可以改进的地方，比如批量计算每个加油站去下一站剩下的油量gas-cost.我们还可以根据给定的值来优先找一些可能值，而不是暴力搜索。
具体代码（python）已对应实现，如上述思路有不足之处请批评指正。