[leedcode 134] Gas Station

2978 단어 code
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, otherwise return -1.
Note:The solution is guaranteed to be unique.
public class Solution {
    /*   0         ,   restGas += gas[i] - cost[i],    i    restGas<0,            beg  ,
          ,            beg+1      ,   beg ,    gas>=cost,
       beg+1   i    gas      cost,                 ,         ,
      i+1      ,    size-1        ,          ,        ,   (total),
               。*/

/*      :             ,        ,     ,    ,          ,       ,                  ,       ;  ,        ,                 ;           ,    。*/
    public int canCompleteCircuit(int[] gas, int[] cost) {
        
        int i=0;
        int left=0;
        int beg=0;
        int total=0;
        while(i<gas.length){
            left+=gas[i]-cost[i];
            total+=gas[i]-cost[i];//total          gas>cost
            if(left<0){
                beg=i+1;
                left=0;
            }
            i++;
        }
        if(total>=0) return beg;
        else return -1;
    }
}

좋은 웹페이지 즐겨찾기