加油站
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i]升。
你有一辆油箱容量无限的的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油 cost[i]升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释: 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
暴力（超时）
以每一个点作为起点试
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int i = 0; i < n; i++) {
int remain = gas[i];
int j = i;
while (remain >= cost[j]) {
remain -= cost[j];
j = (j + 1) % n;
remain += gas[j];
if (i == j) {
return i;
}
}
}
return -1;
}
优化1（超时）
暴力存在很多重复计算
设当前在考虑从 i出发,先初始化 j = i
* * * * * *
^
i
^
j
随后 j 会进行后移
* * * * * *
^ ^
i j
继续后移
* * * * * *
^ ^
i j
继续后移
* * * * * *
^ ^
j i
此时 j 又回到了第 0 个位置，我们在之前已经考虑过了这个位置出发。
如果之前考虑第 0 个位置的时候，最远到了第 2 个位置。
那么此时 j 就可以直接跳到第 2 个位置，同时加上当时的剩余汽油，继续考虑
* * * * * *
^ ^
j i
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
// 从index出发能到达的最远位置和剩余的油量
int[] farIndex = new int[n];
int[] farIndexRemain = new int[n];
Arrays.fill(farIndex, -1);
for (int i = 0; i < n; i++) {
int remain = gas[i];
int j = i;
while (remain >= cost[j]) {
remain -= cost[j];
j = (j + 1) % n;
if (farIndex[j] != -1) {
remain += farIndexRemain[j];
j = farIndex[j];
} else {
remain += gas[j];
}
if (i == j) {
return i;
}
}
farIndex[i] = j;
farIndexRemain[i] = remain;
}
return -1;
}
优化2
我们考虑一下下边的情况。
* * * * * *
^ ^
i j
当考虑 i 能到达的最远的时候，假设是 j。
那么 i + 1 到 j 之间的节点是不是就都不可能绕一圈了？
假设 i + 1 的节点能绕一圈，那么就意味着从 i + 1 开始一定能到达 j + 1。
又因为从 i 能到达 i + 1，所以从 i 也能到达 j + 1。
但事实上，i 最远到达 j 。产生矛盾，所以 i + 1 的节点一定不能绕一圈。同理，其他的也是一样的证明。
所以下一次的 i 我们不需要从 i + 1 开始考虑，直接从 j + 1 开始考虑即可。
还有一种情况，就是因为到达末尾的时候，会回到 0。
如果对于下边的情况。
* * * * * *
^ ^
j i
如果 i 最远能够到达 j ，根据上边的结论 i + 1 到 j 之间的节点都不可能绕一圈了。想象成一个圆，所以 i 后边的节点就都不需要考虑了，直接返回 -1 即可。
贪心
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站到到下一站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int totalSum = 0, curSum = 0;
int start = 0;
for (int i = 0; i < n; i++) {
totalSum += gas[i] - cost[i];
curSum += gas[i] - cost[i];
if (curSum < 0) {
start = i + 1;
curSum = 0;
}
}
return totalSum < 0 ? -1 : start;
}
