134. 加油站

• 第一种想法就是每个位置都遍历一遍 O(n*n)

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int ans[] = new int[gas.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = gas[i] - cost[i];
        }
        for (int i = 0; i < ans.length; i++) {
            int j = 0;
            int temp = 0;
            while (j < ans.length) {
                temp += ans[(i+j)%ans.length];
                if (temp < 0) break;
                j++;
            }
            if(j==ans.length)return i;
        }
        return -1;
    }
}

• 第二种想法 优化上面的代码 也就是找中断点 然后接着后面查找

  class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 加油站起始点
        int start = 0;
        // 从0-start需要补充多少油 
        int total = 0;
        // 从start开始到i 油量   
        int tank = 0;
  
        for(int i=0; i<gas.length; i++) {
            // 走过ith 加油站还剩下多少油 （>0）
            // 要走ith 加油站差多少油 （<0）
            tank += gas[i] - cost[i];
            // 油不够了，start不能做起始点；
            // 且start ～ i 都不可做起始点。
            if(tank < 0) {
                start = i+1;
                total += tank;
                tank = 0;
            }
        }
        return total+tank >= 0 ?start : -1;
    }
  }