134. 加油站
題目連結：https://leetcode-cn.com/problems/gas-station/
在一條環路上有 N 個加油站，其中第 i 個加油站有汽油 gas[i] 升。
你有一輛油箱容量無限的的汽車，從第 i 個加油站開往第 i+1 個加油站需要消耗汽油 cost[i] 升。你從其中的一個加油站出發，開始時油箱為空。
如果你可以繞環路行駛一週，則返回出發時加油站的編號，否則返回 -1。
說明:
如果題目有解，該答案即為唯一答案。輸入陣列均為非空陣列，且長度相同。輸入陣列中的元素均為非負數。示例 1:輸入:gas = [1,2,3,4,5]cost = [3,4,5,1,2]
輸出: 3解釋:從 3 號加油站(索引為 3 處)出發，可獲得 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 號加油站出發，因為沒有足夠的汽油可以讓你行駛到下一個加油站。我們從 2 號加油站出發，可以獲得 4 升汽油。此時油箱有 = 0 + 4 = 4 升汽油開往 0 號加油站，此時油箱有 4 - 3 + 2 = 3 升汽油開往 1 號加油站，此時油箱有 3 - 3 + 3 = 3 升汽油你無法返回 2 號加油站，因為返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。因此，無論怎樣，你都不可能繞環路行駛一週。
思路暴力方法暴力的方法很明顯就是O(n^2)的，遍歷每一個加油站為起點的情況，模擬一圈。
如果跑了一圈，中途沒有斷油，而且最後油量大於等於0，說明這個起點是ok的。
暴力的方法思路比較簡單，但程式碼寫起來也不是很容易，關鍵是要模擬跑一圈的過程。
「for迴圈適合模擬從頭到尾的遍歷，而while迴圈適合模擬環形遍歷，要善於使用while！」
C++程式碼如下：
class Solution {public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { for (int i = 0; i < cost.size(); i++) { int rest = gas[i] - cost[i]; // 記錄剩餘油量 int index = (i + 1) % cost.size(); while (rest > 0 && index != i) { // 模擬以i為起點行駛一圈 rest += gas[index] - cost[index]; index = (index + 1) % cost.size(); } // 如果以i為起點跑一圈，剩餘油量>=0，返回該起始位置 if (rest >= 0 && index == i) return i; } return -1; }};C++暴力解法在leetcode上提交也可以過。
貪心演算法（方法一）直接從全域性進行貪心選擇，情況如下：
情況一：如果gas的總和小於cost總和，那麼無論從哪裡出發，一定是跑不了一圈的情況二：rest[i] = gas[i]-cost[i]為一天剩下的油，i從0開始計算累加到最後一站，如果累加沒有出現負數，說明從0出發，油就沒有斷過，那麼0就是起點。情況三：如果累加的最小值是負數，汽車就要從非0節點出發，從後向前，看哪個節點能這個負數填平，能把這個負數填平的節點就是出發節點。C++程式碼如下：
class Solution {public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int curSum = 0; int min = INT_MAX; // 從起點出發，油箱裡的油量最小值 for (int i = 0; i < gas.size(); i++) { int rest = gas[i] - cost[i]; curSum += rest; if (curSum < min) { min = curSum; } } if (curSum < 0) return -1; // 情況1 if (min >= 0) return 0; // 情況2 // 情況3 for (int i = gas.size() - 1; i >= 0; i--) { int rest = gas[i] - cost[i]; min += rest; if (min >= 0) { return i; } } return -1; }};「其實我不認為這種方式是貪心演算法，因為沒有找出區域性最優，而是直接從全域性最優的角度上思考問題」。
但這種解法又說不出是什麼方法，這就是一個從全域性角度選取最優解的模擬操作。
所以對於本解法是貪心，我持保留意見！
但不管怎麼說，解法畢竟還是巧妙的，不用過於執著於其名字稱呼。
貪心演算法（方法二）可以換一個思路，首先如果總油量減去總消耗大於等於零那麼一定可以跑完一圈，說明 各個站點的加油站 剩油量rest[i]相加一定是大於等於零的。
每個加油站的剩餘量rest[i]為gas[i] - cost[i]。
i從0開始累加rest[i]，和記為curSum，一旦curSum小於零，說明[0, i]區間都不能作為起始位置，起始位置從i+1算起，再從0計算curSum。
如圖：
那麼為什麼一旦[i，j] 區間和為負數，起始位置就可以是j+1呢，j+1後面就不會出現更大的負數？
如果出現更大的負數，就是更新j，那麼起始位置又變成新的j+1了。
而且j之前出現了多少負數，j後面就會出現多少正數，因為耗油總和是大於零的（前提我們已經確定了一定可以跑完全程）。
「那麼區域性最優：當前累加rest[j]的和curSum一旦小於0，起始位置至少要是j+1，因為從j開始一定不行。全域性最優：找到可以跑一圈的起始位置」。
區域性最優可以推出全域性最優，找不出反例，試試貪心！
C++程式碼如下：
class Solution {public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int curSum = 0; int totalSum = 0; int start = 0; for (int i = 0; i < gas.size(); i++) { curSum += gas[i] - cost[i]; totalSum += gas[i] - cost[i]; if (curSum < 0) { // 當前累加rest[i]和 curSum一旦小於0 start = i + 1; // 起始位置更新為i+1 curSum = 0; // curSum從0開始 } } if (totalSum < 0) return -1; // 說明怎麼走都不可能跑一圈了 return start; }};「說這種解法為貪心演算法，才是是有理有據的，因為全域性最優解是根據區域性最優推匯出來的」。
總結對於本題首先給出了暴力解法，暴力解法模擬跑一圈的過程其實比較考驗程式碼技巧的，要對while使用的很熟練。
然後給出了兩種貪心演算法，對於第一種貪心方法，其實我認為就是一種直接從全域性選取最優的模擬操作，思路還是好巧妙的，值得學習一下。
對於第二種貪心方法，才真正體現出貪心的精髓，用區域性最優可以推出全域性最優，進而求得起始位置。
打算從頭開始打卡的錄友，可以在「演算法彙總」這裡找到歷史文章，很多錄友都在從頭打卡，你並不孤單！
-------end-------
我將演算法學習相關的資料已經整理到了Github ：https://github.com/youngyangyang04/leetcode-master，裡面還有leetcode刷題攻略、各個型別經典題目刷題順序、思維導圖看一看一定會有所收穫，如果給你有幫助給一個star支援一下吧！
我是程式設計師Carl，個人主頁：https://github.com/youngyangyang04