題目
在一條環(huán)路上有 N 個(gè)加油站，其中第 i 個(gè)加油站有汽油 gas[i] 升芽偏。
你有一輛油箱容量無限的的汽車，從第 i 個(gè)加油站開往第 i+1 個(gè)加油站需要消耗汽油 cost[i] 升弦讽。你從其中的一個(gè)加油站出發(fā)污尉，開始時(shí)油箱為空。
如果你可以繞環(huán)路行駛一周往产，則返回出發(fā)時(shí)加油站的編號(hào)被碗，否則返回 -1。
說明:
- 如果題目有解仿村，該答案即為唯一答案锐朴。
- 輸入數(shù)組均為非空數(shù)組，且長度相同蔼囊。
- 輸入數(shù)組中的元素均為非負(fù)數(shù)焚志。
題目鏈接：https://leetcode-cn.com/problems/gas-station
樣例
樣例1
輸入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]輸出: 3
解釋:
從 3 號(hào)加油站(索引為 3 處)出發(fā)衣迷，可獲得 4 升汽油。此時(shí)油箱有 = 0 + 4 = 4 升汽油
開往 4 號(hào)加油站酱酬，此時(shí)油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號(hào)加油站壶谒，此時(shí)油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號(hào)加油站，此時(shí)油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號(hào)加油站膳沽，此時(shí)油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號(hào)加油站汗菜，你需要消耗 5 升汽油，正好足夠你返回到 3 號(hào)加油站挑社。
因此陨界，3 可為起始索引。
樣例2
輸入:
gas = [2,3,4]
cost = [3,4,3]輸出: -1
解釋:
你不能從 0 號(hào)或 1 號(hào)加油站出發(fā)滔灶，因?yàn)闆]有足夠的汽油可以讓你行駛到下一個(gè)加油站普碎。
我們從 2 號(hào)加油站出發(fā)，可以獲得 4 升汽油录平。 此時(shí)油箱有 = 0 + 4 = 4 升汽油
開往 0 號(hào)加油站麻车，此時(shí)油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號(hào)加油站，此時(shí)油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號(hào)加油站斗这，因?yàn)榉党绦枰?4 升汽油动猬，但是你的油箱只有 3 升汽油。
因此表箭，無論怎樣赁咙，你都不可能繞環(huán)路行駛一周。
解題思路
（1）暴力法
使用暴力是可以過免钻，題目說只有唯一答案彼水，我們就可以對(duì)每一個(gè)加油站進(jìn)行遍歷。如果該加油站能夠順利的走完一遍所有加油站的話极舔，那么該加油站就是唯一的一個(gè)答案凤覆。但是時(shí)間復(fù)雜度太高了，極端情況下需要對(duì)我們的站進(jìn)行雙重遍歷拆魏，即O(n2)的復(fù)雜度盯桦。參考代碼如下：
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
//思路：可以for循環(huán)對(duì)每個(gè)加油站進(jìn)行一次完整的模擬
//時(shí)間復(fù)雜度大概為n^2，這是下策
//具體實(shí)現(xiàn)思路渤刃，先對(duì)我們的gas和cost進(jìn)行復(fù)制拥峦，保證我們可以進(jìn)行一次循環(huán)，即gas.length循環(huán)
int[] doubleGas = new int[gas.length * 2];
int[] doubleCost = new int[cost.length * 2];
for(int i = 0; i < doubleGas.length; i++){
doubleGas[i] = gas[i % gas.length];
doubleCost[i] = cost[i % cost.length];
}
int res = -1;
for(int i = 0; i < gas.length; i++){
//只能從這里面每一個(gè)站進(jìn)行出發(fā)
int need = 0; //開到下一個(gè)站所需要的汽油卖子，身在初始站略号，所以需要為0
for(int j = i; j < i + gas.length; j++){
//對(duì)后面站進(jìn)行加油并減去去下一個(gè)站的油，如果遇到油不夠的，則立即停止從那么再重新選一個(gè)出發(fā)點(diǎn)
need += doubleGas[j];
need -= doubleCost[j];
if(need < 0) break;
//如果剛好可以走完一個(gè)for循環(huán)玄柠，題目有唯一解氛琢，這就是答案
if(j == (i + gas.length - 1)) res = i;
}
}
return res;
}
}
（2）貪心。上面的代碼總的來說随闪，看起來實(shí)在丑陋。不僅用了額外的空間骚勘，而且時(shí)間復(fù)雜還巨高铐伴。所以我們需要用貪心來寫這一題。其實(shí)就是暴力的原理然后進(jìn)行一定的優(yōu)化俏讹，需要我們?nèi)グl(fā)現(xiàn)一定的優(yōu)化規(guī)律当宴。
我們先來看一個(gè)例子，如下泽疆。
同樣的户矢，我們的加油站也是這樣的。如果一個(gè)加油站循環(huán)一周殉疼，也就是到達(dá)自己的位置梯浪，那么我們可以直接從它可以到達(dá)的最遠(yuǎn)位置的下一個(gè)位置作為出發(fā)點(diǎn)。如果找到可以循環(huán)一周的點(diǎn)的話瓢娜，那么這個(gè)點(diǎn)就是我們的唯一答案出發(fā)點(diǎn)挂洛。下面是參考代碼：
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int i = 0; i < n; i++) {
int j = i;
int res = gas[i];
while (res - cost[j] >= 0) { //汽油足夠消耗
//減去我們消耗的，并加上下一個(gè)加油站給的油
res += gas[(j + 1) % n] - cost[j];
j = (j + 1) % n;
//如果可以循環(huán)一周的話眠砾，說明這就是唯一答案
if (j == i) return i;
}
//最遠(yuǎn)距離繞到了i之前虏劲，所以 i 后邊的點(diǎn)出發(fā)（i - n）都不可能繞一圈了,并且i之前肯定都是遍歷過的，所以直接無解褒颈。
if (j < i) return -1;
//i還是小于j（i <= j < n）柒巫，i 直接跳到 j，外層 for 循環(huán)執(zhí)行 i++谷丸，相當(dāng)于從 j + 1 開始考慮
i = j;
}
//找不到唯一答案
return -1;
}
}
