134. 加油站
在一條環(huán)路上有N個加油站，其中第i個加油站有汽油gas[i]?升。
你有一輛油箱容量無限的的汽車，從第 i 個加油站開往第 i+1?個加油站需要消耗汽油cost[i]?升语淘。你從其中的一個加油站出發(fā)，開始時油箱為空际歼。
如果你可以繞環(huán)路行駛一周惶翻，則返回出發(fā)時加油站的編號，否則返回 -1鹅心。
說明:
如果題目有解吕粗，該答案即為唯一答案。
輸入數(shù)組均為非空數(shù)組旭愧，且長度相同颅筋。
輸入數(shù)組中的元素均為非負(fù)數(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ā)，因?yàn)闆]有足夠的汽油可以讓你行駛到下一個加油站血崭。我們從 2 號加油站出發(fā)卧惜，可以獲得 4 升汽油。 此時油箱有 = 0 + 4 = 4 升汽油開往 0 號加油站夹纫，此時油箱有 4 - 3 + 2 = 3 升汽油開往 1 號加油站咽瓷，此時油箱有 3 - 3 + 3 = 3 升汽油你無法返回 2 號加油站，因?yàn)榉党绦枰?4 升汽油舰讹，但是你的油箱只有 3 升汽油茅姜。因此，無論怎樣月匣，你都不可能繞環(huán)路行駛一周钻洒。
收獲：
這一題又吃了審題的虧，這個路是環(huán)路锄开，就是它的方向只能是一個方向素标，只要確定起點(diǎn)，然后沿著當(dāng)前方向繞一周就行了萍悴，再就是我審題不認(rèn)真头遭，把要求的起點(diǎn)當(dāng)作了整個行駛下來路程了。以下就是我寫的錯誤的代碼癣诱，雖說錯誤计维，但是有多多少少讓我學(xué)會了遞歸調(diào)用。當(dāng)作經(jīng)驗(yàn)把它記錄下來狡刘。
376. 擺動序列
如果連續(xù)數(shù)字之間的差嚴(yán)格地在正數(shù)和負(fù)數(shù)之間交替享潜，則數(shù)字序列稱為擺動序列。第一個差（如果存在的話）可能是正數(shù)或負(fù)數(shù)嗅蔬。少于兩個元素的序列也是擺動序列剑按。
例如疾就，[1,7,4,9,2,5]是一個擺動序列，因?yàn)椴钪?6,-3,5,-7,3)是正負(fù)交替出現(xiàn)的艺蝴。相反,[1,4,7,2,5]和[1,7,4,5,5]不是擺動序列猬腰，第一個序列是因?yàn)樗那皟蓚€差值都是正數(shù)，第二個序列是因?yàn)樗淖詈笠粋€差值為零猜敢。
給定一個整數(shù)序列姑荷，返回作為擺動序列的最長子序列的長度。 通過從原始序列中刪除一些（也可以不刪除）元素來獲得子序列缩擂，剩下的元素保持其原始順序鼠冕。
示例:
輸入:???????????? [1,7,4,9,2,5]
輸出:??????????? 6
解釋:??????????? 整個序列就是一個擺動序列。
輸入:?????????? [1,17,5,10,13,15,10,5,16,8]
輸出:?????????? 7
解釋: ? ? ? ? ? 它的幾個子序列滿足擺動序列胯盯。其中一個是[1,17,10,13,10,16,8]懈费。
輸入:?????????? [1,2,3,4,5,6,7,8,9]
輸出:?????????? 2
進(jìn)階:
你能否用?O(n) 時間復(fù)雜度完成此題?
超時的程序（錯誤）
這個程序不僅超時，而且也是個錯誤的程序博脑。
造成超時的原因是while循環(huán)里面沒有疊加的變量憎乙，導(dǎo)致程序陷入死循環(huán)，造成超時
為什么會錯呢叉趣，因?yàn)閯h除的序列不僅是開頭和結(jié)尾的，還有中間的疗杉，再就是這個題目所要求的是擺動序列最長子序列的長度
正確的程序
時間復(fù)雜度
收獲：
1. nums.reverse() ? ? 這個函數(shù)返回值為null，主要作用是將nums中的元素反轉(zhuǎn)椭蹄，要調(diào)用反轉(zhuǎn)后的list,直接輸入nums就可以直接使用
2.reversed(seq)
? ? 參數(shù) seq -- 要轉(zhuǎn)換的序列，可以是 tuple, string, list 或 range净赴。
? ? 返回值 ??返回一個反轉(zhuǎn)的迭代器绳矩。
3.淺拷貝玖翅，深拷貝翼馆，賦值和傳地址
? ? alist = [1,2,3,4,5]
? ??c=copy.copy(alist) ? ?淺拷貝
? ??d=copy.deepcopy(alist) ?深拷貝 ?
? ? temp = alist ? ? ? ? ? ? ? ? ? ? 傳地址
? ? 歸納：
? ??????（1）直接賦值,只是傳遞對象的引用,原始列表改變，被賦值的temp也會做相同的改變
? ? ? ? ?（2）copy淺拷貝金度，沒有拷貝子對象应媚，所以原始數(shù)據(jù)改變，子對象會改變
? ? ? ? ?（3）深拷貝猜极，包含對象里面的自對象的拷貝中姜，所以原始對象的改變不會造成深拷貝里 ? 任何子元素的改變
可以參考這個博主（毛豆）寫的 ??https://www.cnblogs.com/xueli/p/4952063.html
4. ?此題要求最長子序列，則需要從兩個方面來比較，一個是從列表的頭到尾開始遍歷丢胚，另外一個從列表的尾到頭開始遍歷翩瓜，取最長的子序列，即得到答案
5. ?for i in range(len(nums)) ?携龟，由于在循環(huán)中兔跌，我需要刪除元素，所以峡蟋，i的值是需要在循環(huán)途中更改的坟桅，len(nums)也是動態(tài)的。但是這個for循環(huán)中的i值是不能在循環(huán)途中更改的蕊蝗，所以仅乓，用while替換。簡而言之匿又，靜態(tài)循環(huán)用for 方灾，動態(tài)循環(huán)用while.
6.此題的效率不高，可以考慮是否有別的更優(yōu)的方案解決這個問題碌更。
