虽然题解中的代码经过数据加强以后过不了了, 但是思路很重要, 理解后稍微改动以后就可以过了 !
/**
* @Title: lec134
* @Author 李浩天
* @Date 2024/3/17 下午8:38
* @description:
*/
public class lec134 {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0;
for (int i = 0; i < gas.length; i ++ ) {
sum += gas[i] - cost[i];
}
if (sum < 0) return -1;
int minSum = 0, nowSum = 0;
int ans = 0;
for (int i = 0; i < gas.length; i ++ ) {
nowSum += gas[i] - cost[i];
System.out.println("[debug] i :" + i + " " + "gas[i] - cost[i] : " + (gas[i] - cost[i]));
if (nowSum <= minSum) {
ans = i; // ans最终记录的是最后一个最低的低峰的下标 !
minSum = nowSum;
}
}
// 答案就是这个最低的低峰后(包括这个低峰)循环向后的第一个 (gas[i] - cost[i] > 0) 的加油站 !
int i = ans;
System.out.println("ans = " + ans);
while (true) {
i %= gas.length;
if (gas[i] - cost[i] >= 0) return i;
i ++ ;
}
}
}