題目：

鏈接：LeetCode 134. 加油站
難度：中等

在一條環(huán)路上有 n 個加油站，其中第 i 個加油站有汽油 gas[i] 升。

你有一輛油箱容量無限的的汽車，從第 i 個加油站開往第 i+1 個加油站需要消耗汽油 cost[i] 升。你從其中的一個加油站出發(fā)，開始時油箱為空。

給定兩個整數(shù)數(shù)組 gas 和 cost ，如果你可以繞環(huán)路行駛一周，則返回出發(fā)時加油站的編號，否則返回 -1 。如果存在解，則 保證 它是 唯一 的。

示例 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)路行駛一周。

提示:

• gas.length == n
• cost.length == n
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104

方法一：

函數(shù)圖像法：

sum 代表路途中油箱的油量，如果把這個「最低點」作為起點，即把這個點作為坐標(biāo)軸原點，就相當(dāng)于把圖像「最大限度」向上平移了：

如果經(jīng)過平移后圖像全部在 x 軸以上，就說明可以行使一周。

代碼一：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();int minsum = 0, minpos = 0; //函數(shù)最低點的值，函數(shù)最低點的坐標(biāo)（出發(fā)站編號）int sum = 0;for(int i = 0; i < n; i++){sum += gas[i] - cost[i];if(sum < minsum) {minsum = sum;minpos = i + 1;}}if(sum < 0) return -1;return minpos % n;}
};

時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

方法二：

貪心解法：

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

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

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

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

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

如果把k作為起點的話，相當(dāng)于在站點k時sum = 0，那走到j(luò)時必然有sum < 0，也就是說k肯定不能是起點。

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

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

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

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

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

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

看到冗余計算了嗎？看到優(yōu)化的點了嗎？

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

代碼二：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();for(int i = 0; i < n;){int sum = 0;bool flag = true; //以i為出發(fā)站時能否環(huán)行一周for(int j = i; j < i + n; j++){sum += gas[j % n] - cost[j % n]; //行至第j+1個加油站時，油箱內(nèi)的油量if(sum < 0) {if(j + 1 >= n) return -1; //全部出發(fā)點已遍歷完，未找到可行解i = (j + 1) % n; //無法從第i站到第j+1站，則從中間任意一站都無法到第j+1站。那么以第j+1站為出發(fā)站繼續(xù)檢查flag = false;break;}}if(flag) return i; //以第i站為出發(fā)站可以走完一周，返回i}return -1;}
};

時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。