leetcode经典题目：gas-station_gas station leetcode

题目：

环形路上有n个加油站，第i个加油站的汽油量是gas[i].
你有一辆车，车的油箱可以无限装汽油。从加油站i走到下一个加油站（i+1）花费的油量是cost[i]，你从一个加油站出发，刚开始的时候油箱里面没有汽油。
求从哪个加油站出发可以在环形路上走一圈。返回加油站的下标，如果没有答案的话返回-1。
注意：
答案保证唯一。
1
2
3
4
5

思路：类似于求数组和最大的子序列。累加在每个位置的left+=gas[i]-cost[i].就是在每个位置剩余的油量，如果left一直大于0，则可一直走下去，如果left小于0，那么就从下一位置重新开始计数，并且将之前欠下的多少记录下来。如果最终遍历数组剩下的燃料足以弥补之前不够的，那么就可以到达。

    public int canCompleteCircuit(int[] gas,int[] cost){
      int left=0,start=0,lack=0;
      for(int i=0;i<gas.length;i++){
          left+=gas[i]-cost[i];
          if(left<0){
              lack+=left;
              left=0;
              start=i+1;//因为题目保证有解，所以start最多为length-1
          }
      }
      return start;
    }
1
2
3
4
5
6
7
8
9
10
11
12