解题思路
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0;
int min = 0;
for(int i = 0; i < gas.length; i++){
// 统计加油量和耗油量
sum += gas[i] - cost[i];
min = Math.min(min, sum);
}
// 如果小于0,则不能环绕一周
if(sum < 0)
return -1;
// 此时从起点出发能够环绕一周
if(min >= 0)
return 0;
for(int i = gas.length-1; i >= 0; i--){
int diff = gas[i] - cost[i];
min += diff;
// 如果该点能够将min补充到大于等于0,则该点为起点
if(min >= 0)
return i;
}
return -1;
}
}
与该题十分类似53. 最大子序和
当然也需要借助贪心的思想,如果总加油量和耗油量大于等于0那么总可以环绕一周,我们用diff[i]=gas[i]-cost[i]
得到一个数组,我们找到是该数组的最大子数组和的开始元素索引k,从k出发总能环绕一周。
因为数组是一个环路,我们可以将数组diff复制一份到该数组的末尾,然后用前缀和求出最大子数组和。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// 前缀和
int sum = 0;
// 记录遍历过程中的最小前缀和,初始化为0表示前缀和的首元素是0
int min = 0;
int j = 0;
int k = 0;
int maxSum = 0;
int n = gas.length;
int[] diff = new int[2 * n];
for(int i = 0; i < n; i++){
diff[i] = gas[i] - cost[i];
diff[i+n] = diff[i];
}
for(int i = 0; i < diff.length; i++){
sum += diff[i];
// 求最大子数组,更新下标k
if(sum-min > maxSum){
maxSum = sum-min;
k = j;
}
// min是当前最小的前缀和,j记录最小前缀和的开始元素下标
if(min > sum){
j = i+1;
min = sum;
}
}
if(sum < 0)
return -1;
return k % n;
}
}