今天講一個(gè)貪心的老司機(jī)的故事，就是力扣第 134 題「加油站」：

題目應(yīng)該不難理解，就是每到達(dá)一個(gè)站點(diǎn)i，可以加gas［i］升油，但離開(kāi)站點(diǎn)i需要消耗cost［i］升油，問(wèn)你從哪個(gè)站點(diǎn)出發(fā)，可以兜一圈回來(lái)。

要說(shuō)暴力解法，肯定很容易想到，用一個(gè) for 循環(huán)遍歷所有站點(diǎn)，假設(shè)為起點(diǎn)，然后再套一層 for 循環(huán)，判斷一下是否能夠轉(zhuǎn)一圈回到起點(diǎn)：

int n = gas.length;

for （int start = 0; start 《 n; start++） {

for （int step = 0; step 《 n; step++） {

int i = （start + step） % n;

tank += gas［i］;

tank -= cost［i］;

// 判斷油箱中的油是否耗盡

}

}

很明顯時(shí)間復(fù)雜度是 O（N^2），這么簡(jiǎn)單粗暴的解法一定不是最優(yōu)的，我們?cè)噲D分析一下是否有優(yōu)化的余地。

暴力解法是否有重復(fù)計(jì)算的部分？是否可以抽象出「狀態(tài)」，是否對(duì)同一個(gè)「狀態(tài)」重復(fù)計(jì)算了多次？

我們前文 動(dòng)態(tài)規(guī)劃詳解 說(shuō)過(guò)，變化的量就是「狀態(tài)」。那么觀察這個(gè)暴力窮舉的過(guò)程，變化的量有兩個(gè)，分別是「起點(diǎn)」和「當(dāng)前油箱的油量」，但這兩個(gè)狀態(tài)的組合肯定有不下 O（N^2） 種，顯然沒(méi)有任何優(yōu)化的空間。

所以說(shuō)這道題肯定不是通過(guò)簡(jiǎn)單的剪枝來(lái)優(yōu)化暴力解法的效率，而是需要我們發(fā)現(xiàn)一些隱藏較深的規(guī)律，從而減少一些冗余的計(jì)算。

下面我們介紹兩種方法巧解這道題，分別是數(shù)學(xué)圖像解法和貪心解法。

圖像解法

汽車進(jìn)入站點(diǎn)i可以加gas［i］的油，離開(kāi)站點(diǎn)會(huì)損耗cost［i］的油，那么可以把站點(diǎn)和與其相連的路看做一個(gè)整體，將gas［i］ - cost［i］作為經(jīng)過(guò)站點(diǎn)i的油量變化值：

這樣，題目描述的場(chǎng)景就被抽象成了一個(gè)環(huán)形數(shù)組，數(shù)組中的第i個(gè)元素就是gas［i］ - cost［i］。

有了這個(gè)環(huán)形數(shù)組，我們需要判斷這個(gè)環(huán)形數(shù)組中是否能夠找到一個(gè)起點(diǎn)start，使得從這個(gè)起點(diǎn)開(kāi)始的累加和一直大于等于 0。

如何判斷是否存在這樣一個(gè)起點(diǎn)start？又如何計(jì)算這個(gè)起點(diǎn)start的值呢？

我們不妨就把 0 作為起點(diǎn)，計(jì)算累加和的代碼非常簡(jiǎn)單：

int n = gas.length， sum = 0;

for （int i = 0; i 《 n; i++） {

// 計(jì)算累加和

sum += gas［i］ - cost［i］;

}

sum就相當(dāng)于是油箱中油量的變化，上述代碼中sum的變化過(guò)程可能是這樣的：

顯然，上圖將 0 作為起點(diǎn)肯定是不行的，因?yàn)閟um在變化的過(guò)程中小于 0 了，不符合我們「累加和一直大于等于 0」的要求。

那如果 0 不能作為起點(diǎn)，誰(shuí)可以作為起點(diǎn)呢？

看圖說(shuō)話，圖像的最低點(diǎn)最有可能可以作為起點(diǎn)：

如果把這個(gè)「最低點(diǎn)」作為起點(diǎn)，就是說(shuō)將這個(gè)點(diǎn)作為坐標(biāo)軸原點(diǎn)，就相當(dāng)于把圖像「最大限度」向上平移了。

再加上這個(gè)數(shù)組是環(huán)形數(shù)組，最低點(diǎn)左側(cè)的圖像可以接到圖像的最右側(cè)：

這樣，整個(gè)圖像都保持在 x 軸以上，所以這個(gè)最低點(diǎn) 4，就是題目要求我們找的起點(diǎn)。

不過(guò)，經(jīng)過(guò)平移后圖像一定全部在 x 軸以上嗎？不一定，因?yàn)檫€有無(wú)解的情況：

如果sum（gas［。..］） 《 sum（cost［。..］），總油量小于總的消耗，那肯定是沒(méi)辦法環(huán)游所有站點(diǎn)的。

綜上，我們就可以寫出代碼：

int canCompleteCircuit（int［］ gas， int［］ cost） {

int n = gas.length;

// 相當(dāng)于圖像中的坐標(biāo)點(diǎn)和最低點(diǎn)

int sum = 0， minSum = Integer.MAX_VALUE;

int start = 0;

for （int i = 0; i 《 n; i++） {

sum += gas［i］ - cost［i］;

if （sum 《 minSum） {

// 經(jīng)過(guò)第 i 個(gè)站點(diǎn)后，使 sum 到達(dá)新低

// 所以站點(diǎn) i + 1 就是最低點(diǎn)（起點(diǎn)）

start = i + 1;

minSum = sum;

}

}

if （sum 《 0） {

// 總油量小于總的消耗，無(wú)解

return -1;

}

// 環(huán)形數(shù)組特性

return start == n ？ 0 ： start;

}

以上是觀察函數(shù)圖像得出的解法，時(shí)間復(fù)雜度為 O（N），比暴力解法的效率高很多。

下面我們介紹一種使用貪心思路寫出的解法，和上面這個(gè)解法比較相似，不過(guò)分析過(guò)程不盡相同。

貪心解法

用貪心思路解決這道題的關(guān)鍵在于以下這個(gè)結(jié)論：

如果選擇站點(diǎn)i作為起點(diǎn)「恰好」無(wú)法走到站點(diǎn)j，那么i和j中間的任意站點(diǎn)k都不可能作為起點(diǎn)。

比如說(shuō)，如果從站點(diǎn)1出發(fā)，走到站點(diǎn)5時(shí)油箱中的油量「恰好」減到了負(fù)數(shù)，那么說(shuō)明站點(diǎn)1「恰好」無(wú)法到達(dá)站點(diǎn)5；那么你從站點(diǎn)2，3，4任意一個(gè)站點(diǎn)出發(fā)都無(wú)法到達(dá)5，因?yàn)榈竭_(dá)站點(diǎn)5時(shí)油箱的油量也必然被減到負(fù)數(shù)。

如何證明這個(gè)結(jié)論？

假設(shè)tank記錄當(dāng)前油箱中的油量，如果從站點(diǎn)i出發(fā)（tank = 0），走到j(luò)時(shí)恰好出現(xiàn)tank 《 0的情況，那說(shuō)明走到i， j之間的任意站點(diǎn)k時(shí)都滿足tank 》 0，對(duì)吧。

如果把k作為起點(diǎn)的話，相當(dāng)于在站點(diǎn)k時(shí)tank = 0，那走到j(luò)時(shí)必然有tank 《 0，也就是說(shuō)k肯定不能是起點(diǎn)。

拜托，從i出發(fā)走到k好歹tank 》 0，都無(wú)法達(dá)到j(luò)，現(xiàn)在你還讓tank = 0了，那更不可能走到j(luò)了對(duì)吧。

綜上，這個(gè)結(jié)論就被證明了。

回想一下我們開(kāi)頭說(shuō)的暴力解法是怎么做的？

如果我發(fā)現(xiàn)從i出發(fā)無(wú)法走到j(luò)，那么顯然i不可能是起點(diǎn)。

現(xiàn)在，我們發(fā)現(xiàn)了一個(gè)新規(guī)律，可以推導(dǎo)出什么？

如果我發(fā)現(xiàn)從i出發(fā)無(wú)法走到j(luò)，那么i以及i， j之間的所有站點(diǎn)都不可能作為起點(diǎn)。

看到冗余計(jì)算了嗎？看到優(yōu)化的點(diǎn)了嗎？

這就是貪心思路的本質(zhì)，如果找不到重復(fù)計(jì)算，那就通過(guò)問(wèn)題中一些隱藏較深的規(guī)律，來(lái)減少冗余計(jì)算。

根據(jù)這個(gè)結(jié)論，就可以寫出如下代碼：

int canCompleteCircuit（int［］ gas， int［］ cost） {

int n = gas.length;

int sum = 0;

for （int i = 0; i 《 n; i++） {

sum += gas［i］ - cost［i］;

}

if （sum 《 0） {

// 總油量小于總的消耗，無(wú)解

return -1;

}

// 記錄油箱中的油量

int tank = 0;

// 記錄起點(diǎn)

int start = 0;

for （int i = 0; i 《 n; i++） {

tank += gas［i］ - cost［i］;

if （tank 《 0） {

// 無(wú)法從 start 走到 i

// 所以站點(diǎn) i + 1 應(yīng)該是起點(diǎn)

tank = 0;

start = i + 1;

}

}

return start == n ？ 0 ： start;

}

這個(gè)解法的時(shí)間復(fù)雜度也是 O（N），和之前圖像法的解題思路有所不同，但代碼非常類似。

其實(shí)，你可以把這個(gè)解法的思路結(jié)合圖像來(lái)思考，可以發(fā)現(xiàn)它們本質(zhì)上是一樣的，只是理解方式不同而已。

對(duì)于這種貪心算法，沒(méi)有特別套路化的思維框架，主要還是靠多做題多思考，將題目的場(chǎng)景進(jìn)行抽象的聯(lián)想，找出隱藏其中的規(guī)律，從而減少計(jì)算量，進(jìn)行效率優(yōu)化。

好了，這道題就講到這里，希望對(duì)你拓寬思路有幫助。

責(zé)任編輯：haq