构建剩余油数组;res为相同的两个剩余油数组连接在一起,方便遍历。
指针i指初始加油站。指针j<len+i向后指;剩余油取和。
若到加油站剩余油小于0,将更新指针i到词加油站+1的位置。
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int len = gas.length;
int[] res = new int[2 * len];
for(int i =0;i<gas.length;i++){
res[i] = gas[i] - cost[i];
res[i + len] = gas[i] - cost[i];
}
int point = 0;
while(point < len){
int temp = 0;
for(int i =0;i<len;i++){
temp += res[i + point];
if(temp < 0){
point = i+1+point;
break;
}
}
if(temp >= 0) return point;
}
return -1;
}
}
京公网安备 11010502036488号