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

題目應該不難理解，就是每到達一個站點i，可以加gas［i］升油，但離開站點i需要消耗cost［i］升油，問你從哪個站點出發，可以兜一圈回來。

要說暴力解法，肯定很容易想到，用一個 for 循環遍歷所有站點，假設為起點，然后再套一層 for 循環，判斷一下是否能夠轉一圈回到起點：

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］;

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

}

}

很明顯時間復雜度是 O（N^2），這么簡單粗暴的解法一定不是最優的，我們試圖分析一下是否有優化的余地。

暴力解法是否有重復計算的部分？是否可以抽象出「狀態」，是否對同一個「狀態」重復計算了多次？

我們前文 動態規劃詳解 說過，變化的量就是「狀態」。那么觀察這個暴力窮舉的過程，變化的量有兩個，分別是「起點」和「當前油箱的油量」，但這兩個狀態的組合肯定有不下 O（N^2） 種，顯然沒有任何優化的空間。

所以說這道題肯定不是通過簡單的剪枝來優化暴力解法的效率，而是需要我們發現一些隱藏較深的規律，從而減少一些冗余的計算。

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

圖像解法

汽車進入站點i可以加gas［i］的油，離開站點會損耗cost［i］的油，那么可以把站點和與其相連的路看做一個整體，將gas［i］ - cost［i］作為經過站點i的油量變化值：

這樣，題目描述的場景就被抽象成了一個環形數組，數組中的第i個元素就是gas［i］ - cost［i］。

有了這個環形數組，我們需要判斷這個環形數組中是否能夠找到一個起點start，使得從這個起點開始的累加和一直大于等于 0。

如何判斷是否存在這樣一個起點start？又如何計算這個起點start的值呢？

我們不妨就把 0 作為起點，計算累加和的代碼非常簡單：

int n = gas.length， sum = 0;

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

// 計算累加和

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

}

sum就相當于是油箱中油量的變化，上述代碼中sum的變化過程可能是這樣的：

顯然，上圖將 0 作為起點肯定是不行的，因為sum在變化的過程中小于 0 了，不符合我們「累加和一直大于等于 0」的要求。

那如果 0 不能作為起點，誰可以作為起點呢？

看圖說話，圖像的最低點最有可能可以作為起點：

如果把這個「最低點」作為起點，就是說將這個點作為坐標軸原點，就相當于把圖像「最大限度」向上平移了。

再加上這個數組是環形數組，最低點左側的圖像可以接到圖像的最右側：

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

不過，經過平移后圖像一定全部在 x 軸以上嗎？不一定，因為還有無解的情況：

如果sum（gas［。..］） 《 sum（cost［。..］），總油量小于總的消耗，那肯定是沒辦法環游所有站點的。

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

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

int n = gas.length;

// 相當于圖像中的坐標點和最低點

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） {

// 經過第 i 個站點后，使 sum 到達新低

// 所以站點 i + 1 就是最低點（起點）

start = i + 1;

minSum = sum;

}

}

if （sum 《 0） {

// 總油量小于總的消耗，無解

return -1;

}

// 環形數組特性

return start == n ？ 0 ： start;

}

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

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

貪心解法

用貪心思路解決這道題的關鍵在于以下這個結論：

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

比如說，如果從站點1出發，走到站點5時油箱中的油量「恰好」減到了負數，那么說明站點1「恰好」無法到達站點5；那么你從站點2，3，4任意一個站點出發都無法到達5，因為到達站點5時油箱的油量也必然被減到負數。

如何證明這個結論？

假設tank記錄當前油箱中的油量，如果從站點i出發（tank = 0），走到j時恰好出現tank 《 0的情況，那說明走到i， j之間的任意站點k時都滿足tank 》 0，對吧。

如果把k作為起點的話，相當于在站點k時tank = 0，那走到j時必然有tank 《 0，也就是說k肯定不能是起點。

拜托，從i出發走到k好歹tank 》 0，都無法達到j，現在你還讓tank = 0了，那更不可能走到j了對吧。

綜上，這個結論就被證明了。

回想一下我們開頭說的暴力解法是怎么做的？

如果我發現從i出發無法走到j，那么顯然i不可能是起點。

現在，我們發現了一個新規律，可以推導出什么？

如果我發現從i出發無法走到j，那么i以及i， j之間的所有站點都不可能作為起點。

看到冗余計算了嗎？看到優化的點了嗎？

這就是貪心思路的本質，如果找不到重復計算，那就通過問題中一些隱藏較深的規律，來減少冗余計算。

根據這個結論，就可以寫出如下代碼：

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） {

// 總油量小于總的消耗，無解

return -1;

}

// 記錄油箱中的油量

int tank = 0;

// 記錄起點

int start = 0;

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

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

if （tank 《 0） {

// 無法從 start 走到 i

// 所以站點 i + 1 應該是起點

tank = 0;

start = i + 1;

}

}

return start == n ？ 0 ： start;

}

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

其實，你可以把這個解法的思路結合圖像來思考，可以發現它們本質上是一樣的，只是理解方式不同而已。

對于這種貪心算法，沒有特別套路化的思維框架，主要還是靠多做題多思考，將題目的場景進行抽象的聯想，找出隱藏其中的規律，從而減少計算量，進行效率優化。

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

責任編輯：haq