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.

这个问题可以暴力搜索解决。即，从下标为0的车站开始，如果从该点出发能绕一圈回来，那就返回0；否则就再去尝试下标为1的车站。若从所有车站出发，都不能绕一圈回来的话，那就返回-1。

在此基础上可以做如下的优化：从下标为0的车站开始往前走，如果走到第k个车站的时候，油箱容量首次出现负值，那么就可以断定，如果从第1，2，……，k个车站开始的话，走到第k个车站的时候，邮箱容量肯定也是负值。所以，下一步是从下标为k+1的点往前走，……直到绕一圈回来。

还可以继续优化：首先有如下结论：如果各个车站的gas的容量之和大于等于各个cost之和的话，那么此问题的解必然存在（此结论在后文证明）。所以，可以这么做：首先根据上述结论判断解是否存在，若不存在直接返回-1。若解存在，则只需便利一遍：从下标为0的车站开始往前走，如果走到第k个车站的时候，油箱容量首次出现负值，那么下一步从下标为k+1的点往前走，不用绕一圈回来，只要走到数组末尾即可。例如，走到数组末尾的时候发现，最后一次遇到“油箱容量为负值”的情况是在第m个车站，那么最终返回m+1即可。

“如果各个车站的gas的容量之和大于等于各个cost之和的话，那么此问题的解必然存在”的证明：

为了简化起见，记

arr[i] = gas[i] – cost[i]

记数组的最后一个下标是m

考虑如下的求和

sum(i)=arr[0]+arr[1]+…+arr[i]

如果对任意的i，都有sum(i) > 0，那么此问题的解必然存在。

否则，令i=k是使得sum(i)最小的那个i，

则k+1就是此问题的解。证明如下：

由于sum(k)是最小的，所以
arr[k+1]
arr[k+1]+arr[k+2]
……
arr[k+1]+arr[k+2]+…+arr[m]
都是正数（否则和“sum(k)是最小的”矛盾）

如果求和越过了数组的右边界
对于任意的j<=k，有
arr[k+1]+arr[k+2]+…+arr[m]+(arr[0]+arr[1]+arr[j])
= arr[k+1]+arr[k+2]+…+arr[m]+sum(j)
>=arr[k+1]+arr[k+2]+…+arr[m]+sum(k)
>=0

上式倒数第二个“>=”是因为，sum(k)是最小的

上式的最后一个“>=”是因为，arr的全部元素之和大于等于0