题目解析
由题目中示例一，存在两个数组。
- 一个是
gas = {1, 2, 3, 4, 5}代表了加油站 - 一个是
cost = {3, 4, 5, 1, 2}代表了消耗的汽油 - 需要求证的是，从 索引
i出发是否能够绕行一周回到索引i的位置 - ex：比如从
gas[0]出发，能够获取的油量 = 1想要开往下一个加油站的话需要消耗油量 = 3
- 因此，不能够从 第 0 号加油站出发
- 由此可以得出结论，当
cost[k] > gas[k]的时候，是不能够从第k号加油站出发的 - 所以，唯一的解必定出现在
gas[k] >= cost[k]中
- 那么如果按照题目中给出的计算方法一一计算的话，该种方法可行。
- 但是 时间复杂度没有办法保证
- 果不其然，超时了
show code : 超时了
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
List<Integer> list = new ArrayList<>();
for(int i = 0;i < n;i++) {
if(gas[i] >= cost[i]) {
list.add(i);
}
}
if(list.size() == 1) {
return list.get(0);
}
for(int i : list) {
int sz = n;
int localGas = 0;
// 这个时候从 i 出发判断能够回到 索引 i
int startIdx = i;
while(sz > 0) {
localGas += gas[startIdx];
localGas -= cost[startIdx];
if(localGas < 0) {
// 没有办法到达下一个加油站
break;
}
startIdx++;
if(startIdx == n) {
startIdx = 0;
}
sz--;
}
if(startIdx == i) {
return i;
}
}
return -1;
}
}- 超时的主要原因在于，对于每一个符合条件的出发点，都进行计算验证判断其是否是唯一解。
- 再加上数据量级达到了
，所以超时了。
再接再厉
- 再次仔细观察题目中的用例
- 通过区分 示例1 和 示例2
- 可以发现，当
sum_gas (油的总量) < cost_gas (消耗的总量)的时候，很显然是无法按照顺序 “环路一周的” - 再进行思考，当
sum_gas >= cost_gas的时候有什么特征可以利用吗？
- 想不出来，查看一下题目标签。
- 标签是 贪心+数组 如何运用贪心思维来解决？
- 想不出来，学习其它解。
- 求数组
gas和cost的差前缀和，即gas[i] - cost[i] - 如果最终求得的前缀和
sum < 0很显然无法 “环路一周” sum >= 0的时候，前缀和最小的下一位就是 “唯一解”
- 为什么？
- 求得差前缀和数组之后，记差数组前缀和最小值
min = diff[j] - 结合题意 min 一定是小于 0 的，因为如果 min 大于 0 意味着从任何位置都可以 “环路一周”，就不存在唯一解了
- 为什么 min 对应索引位置的下一个位置是唯一解？
- 倒推
- 从唯一解的位置出发最终再回到唯一解的位置的时候，
油量 >= 0 - 从其它位置出发的时候无法回到出发位置
- 已知：从唯一解出发的时候，油量收益肯定不是负的。
- 从收益角度看，在 min 位置的时候，收益最小，从min 下一个位置开始收益开始为正
show code
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
// 记录两个数组的差前缀和.
int sum = 0;
// 初始化最小值是 0.
int min = 0;
// 记录最小值对应的下一个索引位置.
int idx = 0;
for(int i = 0;i < n;i++) {
sum += gas[i] - cost[i];
if(sum < min) {
min = sum;
idx = i + 1;
}
}
return sum < 0?-1:idx;
}
}一个更好的思路
- 从一个位置开始遍历
- 判断是否能够到达下一个位置
- 如果能，证明油量可能有剩余，那么记录下剩余的油量
- 如果不能，证明油量不够。记录下缺少的油量
- 这个时候记录一下下一个位置，判断是否能够 “环路一种”
show code
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// 记录剩余油
int leftGas = 0;
// 当前点不可达，记录缺少的油
int lackGas = 0;
// 重试的起点——前一个位置不可达的点
int newIdx = 0;
int n = gas.length;
for(int i = 0;i < n;i++) {
// 计算到下一个点，剩多少油
leftGas += gas[i] - cost[i];
if(leftGas < 0) {
// 无法达到下一个点，记录缺少的油量
lackGas += -leftGas;
// 剩余油量重置为 0，从下一个点开始重试出发
newIdx = i + 1;
leftGas = 0;
}
}
// 遍历完成，查看剩余油量是否能够填补空缺，如果能，则找到了唯一解 即 newIdx
return leftGas >= lackGas?newIdx : -1;
}
}