題目描述
這是 LeetCode 上的 「134. 加油站」 竿裂，難度為 「中等」玉吁。
在一條環(huán)路上有?N?個加油站，其中第?i?個加油站有汽油?gas[i]?升腻异。
你有一輛油箱容量無限的的汽車进副，從第 i 個加油站開往第 i+1?個加油站需要消耗汽油?cost[i]?升。你從其中的一個加油站出發(fā)悔常，開始時油箱為空影斑。
如果你可以繞環(huán)路行駛一周，則返回出發(fā)時加油站的編號这嚣，否則返回 -1鸥昏。
說明:
- 如果題目有解，該答案即為唯一答案姐帚。
- 輸入數(shù)組均為非空數(shù)組，且長度相同障涯。
- 輸入數(shù)組中的元素均為非負數(shù)罐旗。
示例?1:
輸入:?
gas??=?[1,2,3,4,5]
cost?=?[3,4,5,1,2]
輸出:?3
解釋:
從 3 號加油站(索引為 3 處)出發(fā)，可獲得 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 可為起始索引匙姜。示例 2:
輸入:?
gas??=?[2,3,4]
cost?=?[3,4,3]
輸出:?-1
解釋:
你不能從?0?號或 1 號加油站出發(fā)畅厢，因為沒有足夠的汽油可以讓你行駛到下一個加油站。
我們從 2 號加油站出發(fā)氮昧，可以獲得 4 升汽油框杜。?此時油箱有?=?0?+ 4 = 4 升汽油
開往?0?號加油站浦楣，此時油箱有?4?-?3?+?2?=?3?升汽油
開往?1?號加油站，此時油箱有?3?-?3?+?3?=?3?升汽油
你無法返回 2 號加油站咪辱，因為返程需要消耗 4 升汽油振劳，但是你的油箱只有 3 升汽油。
因此油狂，無論怎樣历恐，你都不可能繞環(huán)路行駛一周。基本分析/樸素解法
這是一道比較經(jīng)典的題目选调。
估計在 LeetCode 也是有一段時間了夹供，所以連數(shù)據(jù)范圍都沒有。
我這里直接規(guī)定一下數(shù)據(jù)范圍為 仁堪，這意味著我們不能使用 做法了哮洽。
但樸素做法往往是優(yōu)化的出發(fā)點，所以我們還是先分析一下弦聂，樸素的做法是怎么樣的：
-
題目要求「合法起點」的下標鸟辅，因此我們可以枚舉所有的「起點」
-
然后按照「油量 & 成本」模擬一遍，看是否能走完一圈
共有 個「起點」莺葫，檢查某個「起點」合法性的復雜度是 的匪凉。因此整體復雜度為 的。
代碼：
class?Solution?{
????public?int?canCompleteCircuit(int[]?gas,?int[]?cost)?{
????????int?n?=?gas.length;
????????for?(int?start?=?0;?start?<?n;?start++)?{
????????????//?直接跳過第一步都不滿足的起點
????????????if?(gas[start]?<?cost[start])?continue;
????????????//?剩余油量
????????????int?cur?=?gas[start]?-?cost[start];
????????????//?所在位置
????????????int?idx?=?(start?+?1)?%?n;
????????????while?(idx?!=?start)?{
????????????????cur?+=?gas[idx]?-?cost[idx];
????????????????//?如果剩余油量為負數(shù)捺檬，說明無法離開當前位置再层，走到下一位置
????????????????if?(cur?<?0)?break;
????????????????idx?=?(idx?+?1)?%?n;
????????????}
????????????if?(idx?==?start)?return?start;
????????}
????????return?-1;
????}
}- 時間復雜度：
- 空間復雜度：
PS. 在 LeetCode 上提交了一下，是可以過的 ??
KMP/DFA
不考慮我們跳過那些第一步就不滿足的起點的話堡纬，將上述解法中的兩個主要邏輯“單獨”拎出來看聂受，都是無法優(yōu)化的：
- 在沒做任何操作之前，我們無法知道哪些起點是不合法的
- 沒有比 更低的復雜度可以驗證一個起點的合法性
因此只能使用 解法烤镐？
并不是蛋济。單獨看無法優(yōu)化，合在一起則可以：隨著某個起點「合法性驗證」失敗炮叶，我們可以否決掉一些「必然不合法」的方案碗旅。
什么意思呢？
在樸素解法中镜悉，當我們驗證了某個起點 失斔畋佟（無法走完一圈）之后，我們接下來會去嘗試驗證起點 积瞒。
這時候驗證 失敗過程中產(chǎn)生的“信息”川尖，其實并沒有貢獻到之后的算法中。
事實上，起點 驗證失敗叮喳，其實是意味存在某個位置 使得「當前油量」為負數(shù)被芳。而這個位置 就是驗證起點 這過程中產(chǎn)生的“信息”。
它可以產(chǎn)生的價值是：在位置 和位置 之間的所有位置馍悟，都不可能是一個合法起點畔濒。也就是說，隨著起點 驗證失敗锣咒，我們可以否決掉方案不僅僅是位置 侵状，而是 這些位置。
我們可以證明為什么會有這樣的性質(zhì)：
首先毅整，可以明確的是：因為 gas 數(shù)組和 cost 數(shù)組是給定的趣兄，因此每個位置的「凈消耗」是固定的，與從哪個「起點」出發(fā)無關(guān)悼嫉。
凈消耗是指該位置提供的「油量」和「到達下一位置的油耗」艇潭，也就是 gas[i] 和 cast[i] 之間的差值。
證明過程如圖：
因此戏蔑，當有了這個優(yōu)化之后蹋凝，我們每個位置其實只會被遍歷常數(shù)次：當位置 作為「起點」驗證失敗后，驗證過程中遍歷過的位置就不需要再作為「起點」被驗證了总棵。
代碼：
class?Solution?{
????public?int?canCompleteCircuit(int[]?gas,?int[]?cost)?{
????????int?n?=?gas.length;
????????for?(int?start?=?0;?start?<?n;?)?{
????????????if?(gas[start]?<?cost[start])?{
????????????????start++;
????????????}?else?{
????????????????int?cur?=?gas[start]?-?cost[start];
????????????????int?idx?=?start?+?1;
????????????????while?(idx?%?n?!=?start)?{
????????????????????cur?+=?gas[idx?%?n]?-?cost[idx?%?n];
????????????????????if?(cur?<?0)?break;
????????????????????idx++;
????????????????}
????????????????if?(idx?%?n?==?start)?return?start;
????????????????else?start?=?idx;
????????????}
????????}
????????return?-1;
????}
}- 時間復雜度：
- 空間復雜度：
總結(jié)
看到這里鳍寂，你可以已經(jīng)理解了 解法是怎么來的了。
但可能還不清楚這個優(yōu)化思路的本質(zhì)是什么情龄，其實這個優(yōu)化的本質(zhì)與 KMP 為什么可以做到線性匹配如出一轍迄汛。
本質(zhì)都是利用某次匹配（驗證）過程產(chǎn)生的“信息”，來加速之后的匹配（驗證）過程（否決掉一些必然合法的方案）骤视。
在我寫過的 KMP 題解里隔心，有這么一句原話：
?當我們的原串指針從
?i位置后移到j位置，不僅僅代表著「原串」下標范圍為 的字符與「匹配串」匹配或者不匹配尚胞，更是在否決那些以「原串」下標范圍為 為「匹配發(fā)起點」的子集。
所以帜慢，從更本質(zhì)的角度出發(fā)笼裳，這道題其實是一道「KMP」思想應用題，或者說廣泛性的「DFA」題粱玲。
其他
在寫「總結(jié)」部分的時候躬柬，我還特意去看了一下題解區(qū)，沒有人提到過「KMP」和「DFA」抽减，幾乎所有題解都停留在題目標簽「貪心算法」的角度去思考允青。
這是不對的，題目標簽的擬定很大程度取決于「寫這個標簽的人的水平」和「ta 當時看這道題的思考角度」卵沉，是一個主觀的結(jié)果颠锉。
學習算法和數(shù)據(jù)結(jié)構(gòu)法牲，應該是去理解每個算法和數(shù)據(jù)結(jié)構(gòu)的“某個操作”為什么能夠帶來優(yōu)化效果，并將該優(yōu)化效果的“底層思想”挖掘出來琼掠，應用到我們沒見過的問題中拒垃，這才是真正的“學習”。
最后
這是我們「刷穿 LeetCode」系列文章的第 No.134 篇瓷蛙，系列開始于 2021/01/01悼瓮，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題艰猬，我們將先將所有不帶鎖的題目刷完横堡。
在這個系列文章里面，除了講解解題思路以外冠桃，還會盡可能給出最為簡潔的代碼命贴。如果涉及通解還會相應的代碼模板。
為了方便各位同學能夠電腦上進行調(diào)試和提交代碼腊满，我建立了相關(guān)的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 套么。
在倉庫地址里，你可以看到系列文章的題解鏈接碳蛋、系列文章的相應代碼胚泌、LeetCode 原題鏈接和其他優(yōu)選題解。
本文使用 文章同步助手 同步
