通知：一些錄友基礎比較薄弱，不知道從哪裡開始刷題。可以看一下公眾號左下角的「算法匯總」，「算法匯總」已經把題目順序編排好了，文章順序即刷題順序，這是全網最詳細的刷題順序了，方便錄友們從頭打卡學習，「算法匯總」會持續更新！
❞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使用的很熟練。
然後給出了兩種貪心算法，對於第一種貪心方法，其實我認為就是一種直接從全局選取最優的模擬操作，思路還是好巧妙的，值得學習一下。
對於第二種貪心方法，才真正體現出貪心的精髓，用局部最優可以推出全局最優，進而求得起始位置。
就醬，「代碼隨想錄」值得推薦給身邊每一位學習算法的同學朋友，很多錄友關注後都感覺相見恨晚！