? ? ? ? 貪心算法的第三篇博客，繼續腦筋風暴！

134. 加油站

寫在前面

????????這道題規定了有解的話，必定為唯一解

貪心思路

直接從全局進行貪心選擇，情況如下：

• 情況一：如果gas的總和小于cost總和，那么無論從哪里出發，一定是跑不了一圈的

• 情況二：rest[i] = gas[i]-cost[i]為一天剩下的油，i從0開始計算累加到最后一站，如果累加沒有出現負數，說明從0出發，油就沒有斷過，那么0就是起點。

• 情況三：如果累加的最小值是負數，汽車就要從非0節點出發，從后向前，看哪個節點能把這個負數填平，能把這個負數填平的節點就是出發節點。

????????這種解法其實說不出是什么方法，這就是一個從全局角度選取最優解的模擬操作。

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:curSum = 0  # 當前累計的剩余油量minFuel = float('inf')  # 從起點出發，油箱里的油量最小值for i in range(len(gas)):rest = gas[i] - cost[i]curSum += restif curSum < minFuel:minFuel = curSumif curSum < 0:return -1  # 情況1：整個行程的總消耗大于總供給，無法完成一圈if minFuel >= 0:return 0  # 情況2：從起點出發到任何一個加油站時油箱的剩余油量都不會小于0，可以從起點出發完成一圈for i in range(len(gas) - 1, -1, -1):rest = gas[i] - cost[i]minFuel += restif minFuel >= 0:return i  # 情況3：找到一個位置使得從該位置出發油箱的剩余油量不會小于0，返回該位置的索引return -1  # 無法完成一圈

貪心算法的另外一種理解

????????其實核心內容和上面的方法是一樣的，不過是沒有計算總油量盈余，轉而使用負數逼近的方法：

????????i從0開始累加rest[i]，和記為curSum，一旦curSum小于零，說明[0, i]區間都不能作為起始位置，因為這個區間選擇任何一個位置作為起點，到i這里都會斷油，那么起始位置從i+1算起（重新作為起點），再從0計算curSum。

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:curSum = 0  # 當前累計的剩余油量totalSum = 0  # 總剩余油量start = 0  # 起始位置for i in range(len(gas)):curSum += gas[i] - cost[i]totalSum += gas[i] - cost[i]if curSum < 0:  # 當前累計剩余油量curSum小于0start = i + 1  # 起始位置更新為i+1curSum = 0  # curSum重新從0開始累計if totalSum < 0:return -1  # 總剩余油量totalSum小于0，說明無法環繞一圈return start

for循環——常規思路

????????挨個作為起點累加計算，未出現負數即ok

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:for i in range(len(cost)):rest = gas[i] - cost[i]  # 記錄剩余油量index = (i + 1) % len(cost)  # 下一個加油站的索引while rest > 0 and index != i:  # 模擬以i為起點行駛一圈（如果有rest==0，那么答案就不唯一了）rest += gas[index] - cost[index]  # 更新剩余油量index = (index + 1) % len(cost)  # 更新下一個加油站的索引if rest >= 0 and index == i:  # 如果以i為起點跑一圈，剩余油量>=0，并且回到起始位置return i  # 返回起始位置ireturn -1  # 所有起始位置都無法環繞一圈，返回-1

135. 分發糖果

????????本題采用了兩次貪心的策略：

• 一次是從左到右遍歷，只比較右邊孩子評分比左邊大的情況。
• 一次是從右到左遍歷，只比較左邊孩子評分比右邊大的情況。

????????這樣從局部最優推出了全局最優，即：相鄰的孩子中，評分高的孩子獲得更多的糖果。

class Solution:def candy(self, ratings: List[int]) -> int:n = len(ratings)candies = [1] * n# Forward pass: handle cases where right rating is higher than leftfor i in range(1, n):if ratings[i] > ratings[i - 1]:candies[i] = candies[i - 1] + 1# Backward pass: handle cases where left rating is higher than rightfor i in range(n - 2, -1, -1):if ratings[i] > ratings[i + 1]:candies[i] = max(candies[i], candies[i + 1] + 1)return sum(candies)

860.檸檬水找零

? ? ? ? 本以為累加即可，但其實是不對的，因為存在10美分和5美分的區別，所以不能混為一談

????????局部最優：遇到賬單20，優先消耗美元10，完成本次找零。全局最優：完成全部賬單的找零。

????????這道題告訴我們，不要總是想判斷總數，可以把每個單獨的數字列成參數，分別處理

class Solution:def lemonadeChange(self, bills: List[int]) -> bool:five = 0ten = 0twenty = 0for bill in bills:# 情況一：收到5美元if bill == 5:five += 1# 情況二：收到10美元if bill == 10:if five <= 0:return Falseten += 1five -= 1# 情況三：收到20美元if bill == 20:# 先嘗試使用10美元和5美元找零if five > 0 and ten > 0:five -= 1ten -= 1#twenty += 1# 如果無法使用10美元找零，則嘗試使用三張5美元找零elif five >= 3:five -= 3#twenty += 1else:return Falsereturn True

406.根據身高重建隊列

????????重點理解排序！這兩個排序很重要！

class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:# 默認升序# -x[0]：對第一個值取負，實現降序排列（數值越大越靠前）。# x[1]：第二個值保持原值，實現升序排列（數值越小越靠前）。people.sort(key=lambda x: (-x[0], x[1]))que = []# 具體是先處理身高較高的，在身高相同的情況下，優先處理 k 值較小的。# 這兩個排序必不可少！！# 因為身高已經是高->低, 低對高無影響, 所以低身高直接根據K值插入即可# 同時相同K值, 需要從低->高依次處理, 因為后面的插入必須要在大索引的位置, 不能影響之前插入的元素for p in people:que.insert(p[1], p)# list.insert(index, element)# index：插入位置的索引# element：要插入的元素return que

底層實現補充（C++）

????????使用vector是非常費時的，C++中vector（可以理解是一個動態數組，底層是普通數組實現的）如果插入元素大于預先普通數組大小，vector底部會有一個擴容的操作，即申請兩倍于原先普通數組的大小，然后把數據拷貝到另一個更大的數組上。

????????所以使用vector（動態數組）來insert，是費時的，插入再拷貝的話，單純一個插入的操作就是O(n^2)了，甚至可能拷貝好幾次，就不止O(n^2)了。

? ? ? ? 可以使用鏈表代替