在一条环路上有?n?个加油站，其中第?i?个加油站有汽油?gas[i]?升。

你有一辆油箱容量无限的的汽车，从第?i?个加油站开往第?i+1?个加油站需要消耗汽油?cost[i]?升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组?gas?和?cost?，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回?-1?。如果存在解，则?保证?它是?唯一?的。

示例?1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

1、暴力解法；

暴力的方法很明显就是O(n^2)的，遍历每一个加油站为起点的情况，模拟一圈。

如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。

暴力的方法思路比较简单，但代码写起来也不是很容易，关键是要模拟跑一圈的过程。

for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！

public int canCompleteCircuit(int[] gas, int[] cost) {
        for (int i=0;i<gas.length;i++){
            int rest=gas[i]-cost[i];//从i开始油箱第一次剩余的油量
            int index=(i+1)%gas.length;//车子的下标，i位置我们已经走过了
            while (rest>0&&index!=i){//只有油箱的剩余油量大于0 才可以继续往下走
                rest+=gas[i]-cost[i];//得到的减去消耗的就是剩余的
                index=(index+1)%gas.length;
            }
            if (rest>=0&&index==i) return i;//如果走完一圈发现可以走下来，就返回以当前起点为初始点
        }
        //如果所有的下标都走完了都没找到这个起点
        return -1;
    }

2、贪心算法：

可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明各个站点的加油站剩油量rest[i]相加一定是大于等于零的。

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。（题解来源：代码随想录）

?

那么为什么一旦[i，j] 区间和为负数，起始位置就可以是j+1呢，j+1后面就不会出现更大的负数？

如果出现更大的负数，就是更新j，那么起始位置又变成新的j+1了。

而且j之前出现了多少负数，j后面就会出现多少正数，因为耗油总和是大于零的（前提我们已经确定了一定可以跑完全程）。

那么局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置。

代码如下：

 public int canCompleteCircuit(int[] gas, int[] cost) {
       int start=0;//开始点
       int totalSum=0;//总的油箱剩余油量
       int curSum=0;//维持正数的油箱
       for (int i=0;i<gas.length;i++){
           totalSum+=gas[i]-cost[i];
           curSum+=gas[i]-cost[i];
           if (curSum<0){
               curSum=0;
               start=(i+1)%gas.length;//i之前肯定都回不到起点
           }
       }
       if (totalSum<0){//如果总的油箱是负数，说明不论从哪里出发都回不到起点
           return -1;
       }
       return start;
    }

3、图解贪心

以该题为例：
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

下图的黑色折线图即总油量剩余值，若要满足题目的要求：跑完全程再回到起点，总油量剩余值的任意部分都需要在X轴以上，且跑到终点时：总剩余汽油量 >= 0。

为了让黑色折线图任意部分都在 X 轴以上，我们需要向上移动黑色折线图，直到所有点都在X轴或X轴以上。此时，处在X轴的点即为出发点。即黑色折线图的最低值的位置：index = 3。

?这个图是从0点（i=0,即第一个站）出发的折线图，那么改变出发点时，这个图会怎么变化呢？你可以自己去画一画，你会发现，整体折线图的形状是没有变的，改变的是y值，相当于将折线图在Y轴方向上上下平移。那么，当最小点落在X轴上时（也就是使得最小点y=0时），整体折线在X轴上方，y值恒大于等于0，也就是剩余油量一直不为负，可以绕行一圈。对于本例，也就是使得i=3时，y=0。此时，意味着从i=3，第四个站出发，到此站时即没有加油也没有耗油，剩余油量为0。

代码如下：

public int canCompleteCircuit(int[] gas, int[] cost) {
       int min=Integer.MAX_VALUE;//为了记录油箱最低时的时刻
        int minIndex=0;//记录油箱最低时的下标
        int totalSum=0;//油箱的油量
        for (int i=0;i<gas.length;i++){
            totalSum+=gas[i]-cost[i];
            if (totalSum<min){
                min=totalSum;//记录最低油箱的时候
                minIndex=i;//记录最低点的下标
            }
        }
        if (totalSum<0){//说明无论从哪一点出发，都无法到达终点！
            return -1;
        }
        return (minIndex+1)%gas.length;
    }

这道题其实对初入贪心的同学来说还是有点难度的但它确实是一道很巧妙的贪心题目。最后送给大家一句话，也是这道题的核心。