【算法】（Python）贪心算法

贪心算法：

• 又称贪婪算法，greedy algorithm。
• 贪心地追求局部最优解，即每一步当前状态下最优选择。
• 试图通过各局部最优解达到最终全局最优解。但不从整体最优上考虑，不一定全局最优解。
• 步骤：从初始状态拆分成一步一步的，每一步确保当前状态最优解，再下一步。
• 关键：具体的贪心策略（选择能产生问题最优解的最优度量标准）。
• 使用条件：贪心选择（一个问题最优解可通过一系列局部最优解达到，每一步可依赖以前的选择，不可回溯），最优子结构（一个问题最优解包含其子问题的最优解）。

案例：

1、（难度：简单）【力扣】1710. 卡车上的最大单元数

 解题思路：每一步优先挑选当前可装载的最大单元数量的箱子。

1. 将列表按单元数量（元素中下标为1的值）降序排列。
2. 遍历列表中所有元素，
3. 若当前元素的箱子最大数量已经达到指定总数量，则单元总数=指定总数量*单元数量，并结束，返回单元总数。
4. 若当前箱子最大数量在指定总数量之内，则当前箱子最大数量*单元数量，累加到单元总数中，剩余指定总数量=指定总数量-当前箱子最大数量；
5. 再判断列表中下一个元素，
6. 直到遍历完列表中所有元素，或者达到指定总数量，返回单元总数。

 知识点：列表.sort(key=排序条件, reverse=True)：列表按照排序条件降序排列。

class Solution:def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:# 将列表按单元数量（即各元素下标为1的值）降序排列boxTypes.sort(key=lambda x: x[1], reverse=True)total = 0         # 记录可装载的单元总数# 遍历列表，指定最大数量依次减去最大箱子数量计算剩余数量，并统计单元总数# i为箱子数量，j为每个箱子的单元数量for i, j in boxTypes:if i >= truckSize:total += truckSize * jbreaktotal += i * jtruckSize -= ireturn total

2、（难度：中等）【力扣】714. 买卖股票的最佳时机含手续费

解题思路：买卖为一次交易、计算一次手续费，则买入时计算手续费。买入价尽可能当前最低价，卖出价尽可能当前最高价。

1. 初始买入价为列表第一日价格（含手续费），
2. 依次遍历列表中每日价格，
3. 若当前价（含手续费）<买入价，即当前价格比前一天低，则当前价（含手续费）为新的买入价。若当前价（不含手续费）>买入价，则假装卖出，计算利润（若前一日也假装卖出则利润加上当前价与前一日的差价），并假装当天免手续费买入，即当天价（不含手续费）为买入价，
4. 下一日价格，当前价再与买入价比较。
5. 遍历完列表所有元素，返回总利润。

class Solution:def maxProfit(self, prices: List[int], fee: int) -> int:profit = 0                # 记录总收益buy = prices[0] + fee     # 初始买入# 遍历每个价格for i in prices:# 若当前价+手续费<买入价，则当前价买入if i + fee < buy:buy = i + fee# 当前价格>买入价，（假装卖出）计算利润（当前价与买入价的差），# 并假装以当前价免手续费买入（若明天价比当前价高，明天收益就是明天价与当前价之间的差）elif i > buy:profit += (i - buy)buy = ireturn profit

注：本题其他解题方法：动态规划。本文忽略。

3、（难度：困难）【力扣】871. 最低加油次数

解题思路：一个优先队列记录每个加油站的加油量（降序，最大油量在前）。计算每到一个地方的剩余油量，若不足则优先使用最大油量加油。

1. 遍历每个地方和目的地（n+1），
2. 计算从上一个位置到达当前地方后的剩余油量，
3. 若剩余油量不足，则依次从优先队列取出最大油量加油，每加一次统计一次，直到加满或优先队列为空（即没有油可加），
4. 若加完油后剩余油量仍不足，则无法到达目的地，返回-1，
5. 每到达一个加油站，将加油量添加到优先队列，并将当前地方设为上一位置，用于下一个地方计算判断油量。

 知识点：二维数组[子数组下标][子数组中元素下标]：获取二维数组中元素。二维数组：数组中的元素类型仍为数组。

               python中heapq库用于操作堆（最小堆，最大堆），应用于优先队列和堆排序。此处为优先队列。

               heapq.heappush(队列, 元素)：往优先队列添加元素，自动生成最小堆（父节点小于所有子节点，左右子节点无大小要求）。元素前加负号“-”，则各元素负数后的最小堆，类似最大堆，取出时前面也加负号“-”即为最大值。

               heapq.heappop(队列)：从优先队列中取出最小值。

class Solution:def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:       import heapqres = 0               # 统计加油次数fuel_list = []        # 油量优先队列（最大的在前），记录每个加油站的加油量fuel = startFuel      # 记录目前油量pre = 0               # 记录上一个位置# 遍历每个加油站和目的地n = len(stations)for i in range(n + 1):# 记录当前位置,若加油站则为元素中下标为0的值，若目的地则为targetif i < n: cur = stations[i][0]else: cur = target# 计算达到当前位置，剩余油量fuel -= cur - pre# 若剩余油量<0,且油量优先队列中有元素，依次按最大油量加油，直到加满或油量优先队列为空while fuel < 0 and fuel_list:# 油量优先队列为了从大到小排列，元素是负数fuel += (-heapq.heappop(fuel_list))           # 从优先队列取出最大值res += 1# 若加油后，剩余油量仍<0，说明即使加满油也到不了目的地if fuel < 0: return -1# 每到一个加油站，将油量添加到油量优先队列中if i < n:# 油量优先队列为了从大到小排列，元素是负数heapq.heappush(fuel_list, -stations[i][1])    # 添加到优先队列（最大堆）pre = curreturn res

以上是从上次位置到达该加油站后剩余油量判断，也可以直接判断从起始位置到达各加油站时油量是否充足，若不足则取出油量优先队列的最大值加油。

class Solution:def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:import heapqh = []         # 油量优先队列（最大的在前），记录每个加油站的加油量res = 0        # 统计加油次数# 遍历每个加油站和目的地for long, fuel in stations + [[target, 0]]:# 若油量不够，则从优先队列取出最大油量加油while startFuel < long:# 若优先队列为空（即没有油可加），即无法到达目的地if not h: return -1startFuel -= heapq.heappop(h)res += 1# 每到一个加油站，就将油量添加到优先队列heapq.heappush(h, -fuel)return res

注：本题其他解题方法：动态规划。本文忽略。