134. 加油站

image.png

用的是贪心算法

image.png

暴力解法：从每一个节点开始走，看看能不能走到最后（时间复杂度是n^2)
1：把加油和消耗的油分别加起来，如果总油量大于等于消耗量，那有走完的可能性，一旦小于的话，直接return -1

image.png
2：如图，暴力解法假设从第一个节点开始走，如果到第三个节点发现走不通，会break，来从第二个节点开始遍历，但在贪心算法里，我们直接从第三个节点开始走。
这样会假设从第二个节点开始走，其实，肯定走不通，时间复杂度走一圈就行，为O（n）
为什么有这样的假设呢？

因为第一个节点能到第三个节点，就说明，第一个节点肯定能到第二个节点，说明在到达第二个节点的油量是大于等于0的，如果直接从第二个节点出发，单靠油箱的油，肯定无法到达啊，之前的油量为0（很简单的逻辑）
该题的结果就是最后一个出现不满足的条件的点，就是最终答案，为什么不用来验证之后的点呢？
同理，既然后边的点能够走到起始点，那在它之前的点肯定也能走完
具体流程：
1：把油和消耗都分别加起来，如果消耗大，那么直接return -1
2：接下来，遍历整个数组，currentgas代表当前油量，currentgas=currentgas-cost+gas，如果currentgas<0,就代表从下一个节点开始找，最后那个这样的点就是我们要找的起点

注意：题目已经说了，这样的点只能存在一个，所以最后一个这样的点就是起点

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
      int totalgas=0;
      int totalcost=0;
      for(int i=0;i<gas.length;i++){
          totalcost=totalcost+cost[i];
          totalgas=totalgas+gas[i];
      }
      if(totalgas<totalcost) return -1;
      int currentgas=0;//代表当前油量
      int start=0;
      for(int i=0;i<gas.length;i++){
          currentgas=currentgas+gas[i]-cost[i];
          if(currentgas<0){
              currentgas=0;//一旦小于0，要将currentgas初始化为0，从i+1个节点从新开始
              start=i+1;
          }
      }
      return start;
    }
}