加油站
在一條環(huán)路上有 n 個(gè)加油站嗅回，其中第 i 個(gè)加油站有汽油 gas[i]升盒至。
你有一輛油箱容量無(wú)限的的汽車(chē)，從第i個(gè)加油站開(kāi)往第i+1個(gè)加油站需要消耗汽油 cost[i]升盐捷。你從其中的一個(gè)加油站出發(fā)，開(kāi)始時(shí)油箱為空阴孟。
給定兩個(gè)整數(shù)數(shù)組 gas 和 cost 喂击，如果你可以繞環(huán)路行駛一周，則返回出發(fā)時(shí)加油站的編號(hào)锌雀，否則返回 -1 蚂夕。如果存在解，則 保證 它是 唯一 的腋逆。
示例 1:
輸入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
輸出: 3
解釋: 從 3 號(hào)加油站(索引為 3 處)出發(fā)婿牍，可獲得 4 升汽油。此時(shí)油箱有 = 0 + 4 = 4 升汽油
開(kāi)往 4 號(hào)加油站惩歉，此時(shí)油箱有 4 - 1 + 5 = 8 升汽油
開(kāi)往 0 號(hào)加油站等脂，此時(shí)油箱有 8 - 2 + 1 = 7 升汽油
開(kāi)往 1 號(hào)加油站俏蛮，此時(shí)油箱有 7 - 3 + 2 = 6 升汽油
開(kāi)往 2 號(hào)加油站，此時(shí)油箱有 6 - 4 + 3 = 5 升汽油
開(kāi)往 3 號(hào)加油站上遥，你需要消耗 5 升汽油搏屑，正好足夠你返回到 3 號(hào)加油站。
因此粉楚，3 可為起始索引辣恋。
暴力（超時(shí)）
以每一個(gè)點(diǎn)作為起點(diǎn)試
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;
}
優(yōu)化1（超時(shí)）
暴力存在很多重復(fù)計(jì)算
設(shè)當(dāng)前在考慮從 i出發(fā),先初始化 j = i
* * * * * *
^
i
^
j
隨后 j 會(huì)進(jìn)行后移
* * * * * *
^ ^
i j
繼續(xù)后移
* * * * * *
^ ^
i j
繼續(xù)后移
* * * * * *
^ ^
j i
此時(shí) j 又回到了第 0 個(gè)位置，我們?cè)谥耙呀?jīng)考慮過(guò)了這個(gè)位置出發(fā)解幼。
如果之前考慮第 0 個(gè)位置的時(shí)候抑党，最遠(yuǎn)到了第 2 個(gè)位置。
那么此時(shí) j 就可以直接跳到第 2 個(gè)位置撵摆，同時(shí)加上當(dāng)時(shí)的剩余汽油底靠，繼續(xù)考慮
* * * * * *
^ ^
j i
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
// 從index出發(fā)能到達(dá)的最遠(yuǎn)位置和剩余的油量
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;
}
優(yōu)化2
我們考慮一下下邊的情況。
* * * * * *
^ ^
i j
當(dāng)考慮 i 能到達(dá)的最遠(yuǎn)的時(shí)候特铝，假設(shè)是 j暑中。
那么 i + 1 到 j 之間的節(jié)點(diǎn)是不是就都不可能繞一圈了？
假設(shè) i + 1 的節(jié)點(diǎn)能繞一圈鲫剿，那么就意味著從 i + 1 開(kāi)始一定能到達(dá) j + 1鳄逾。
又因?yàn)閺?i 能到達(dá) i + 1，所以從 i 也能到達(dá) j + 1灵莲。
但事實(shí)上雕凹，i 最遠(yuǎn)到達(dá) j 。產(chǎn)生矛盾政冻，所以 i + 1 的節(jié)點(diǎn)一定不能繞一圈枚抵。同理，其他的也是一樣的證明明场。
所以下一次的 i 我們不需要從 i + 1 開(kāi)始考慮汽摹，直接從 j + 1 開(kāi)始考慮即可。
還有一種情況苦锨，就是因?yàn)榈竭_(dá)末尾的時(shí)候逼泣，會(huì)回到 0。
如果對(duì)于下邊的情況舟舒。
* * * * * *
^ ^
j i
如果 i 最遠(yuǎn)能夠到達(dá) j 拉庶，根據(jù)上邊的結(jié)論 i + 1 到 j 之間的節(jié)點(diǎn)都不可能繞一圈了。想象成一個(gè)圓魏蔗，所以 i 后邊的節(jié)點(diǎn)就都不需要考慮了砍的，直接返回 -1 即可。
貪心
首先如果總油量減去總消耗大于等于零那么一定可以跑完一圈莺治，說(shuō)明 各個(gè)站點(diǎn)的加油站 剩油量rest[i]相加一定是大于等于零的廓鞠。
每個(gè)加油站到到下一站的剩余量rest[i]為gas[i] - cost[i]帚稠。
i從0開(kāi)始累加rest[i]，和記為curSum床佳，一旦curSum小于零滋早，說(shuō)明[0, i]區(qū)間都不能作為起始位置，起始位置從i+1算起砌们，再?gòu)?計(jì)算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;
}
