贪心算法的第三篇博客，继续脑筋风暴！
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 += rest
if curSum < minFuel:
minFuel = curSum
if 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 += rest
if 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小于0
start = i + 1 # 起始位置更新为i+1
curSum = 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 # 返回起始位置i
return -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 left
for 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 right
for 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 = 0
ten = 0
twenty = 0
for bill in bills:
# 情况一：收到5美元
if bill == 5:
five += 1
# 情况二：收到10美元
if bill == 10:
if five <= 0:
return False
ten += 1
five -= 1
# 情况三：收到20美元
if bill == 20:
# 先尝试使用10美元和5美元找零
if five > 0 and ten > 0:
five -= 1
ten -= 1
#twenty += 1
# 如果无法使用10美元找零，则尝试使用三张5美元找零
elif five >= 3:
five -= 3
#twenty += 1
else:
return False
return True406.根据身高重建队列
重点理解排序！这两个排序很重要！
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)了。
可以使用链表代替