455. 分发饼干
贪心算法，为了尽可能多的满足，需要用尽可能小的饼干匹配小胃口的孩子。
所以就先拿最小的饼干，尝试匹配最小的胃口，如果匹配上了，那就结果+1，跳过这对，继续；如果下一个没匹配上，说明饼干小了，就跳过这个饼干；如果遍历完饼干还没有匹配上，那就是孩子胃口太大了，没有单个饼干能满足。
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
# 结果
res = 0
# 排序
g.sort()
s.sort()
# 不同数组的索引
index_g, index_s = 0,0
# 遍历，依次用最小的饼干去匹配最小的胃口，看能匹配多少
while index_g < len(g) and index_s < len(s):
# 成功匹配，跳过当前饼干和胃口
if g[index_g] <= s[index_s]:
res += 1
index_g += 1
index_s += 1
# 没有成功匹配，只能继续找大点的饼干
else:
index_s += 1
return res
问题的目标是找出能满足尽可能多小朋友胃口的饼干数量。每个小朋友只能得到一块饼干，且饼干的大小必须大于或等于小朋友的胃口值。这里给出的解决方案是贪心算法的典型应用，旨在通过局部最优解的方式达到全局最优解。下面是对代码的详细解释：
排序：
- 首先，对两个数组
g（小朋友的胃口值数组）和s（饼干大小数组）进行排序。这样做的目的是为了让我们能从最小的胃口值和最小的饼干大小开始配对，符合贪心算法选择每一步的局部最优解，从而尽可能满足更多的小朋友。初始化索引和结果变量：
index_g和index_s分别用于跟踪当前考虑的小朋友和饼干的索引。res用于记录能满足的小朋友数量，初始值为0。遍历并尝试分配饼干：
- 使用
while循环同时遍历胃口值数组g和饼干大小数组s，直到其中一个数组全部考虑完毕。- 在每次循环中，比较当前小朋友的胃口值
g[index_g]和当前饼干的大小s[index_s]：
- 如果
g[index_g] <= s[index_s]，说明当前饼干能满足当前小朋友的胃口，因此增加res的值，并且同时将两个索引index_g和index_s向前移动，表示这个小朋友已经被满足，这块饼干也已经被使用。- 如果当前饼干不能满足当前小朋友的胃口（
g[index_g] > s[index_s]），则只将index_s向前移动，寻找更大的饼干尝试满足当前小朋友的胃口。返回结果：
- 循环结束后，
res中存储的是能够被满足的小朋友的最大数量，将其作为函数的返回值。这种解决方案之所以有效，是因为它总是尝试用最小的饼干去满足胃口最小的小朋友。通过这种方式，我们能确保饼干的使用是最优的，即不会浪费大饼干满足小胃口，从而最大化满足小朋友的数量。
435. 无重叠区间
按照结束时间排序区间。
遍历每个区间，如果当前区间的开始时间小于上一个区间的结束时间，则表示这两个区间重叠，我们需要做出移除操作（即res += 1）。
如果当前区间和上一个区间不重叠，则将start更新为当前区间，继续遍历后续区间。
通过这种方法，我们能最小化需要移除的区间数量，以保证剩余区间互不重叠
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
# 根据右端点进行排序
intervals.sort(key=lambda x:x[1])
# 结果
res = 0
# 当前元素
start = intervals[0]
# 遍历后面的元素
for i in range(1, len(intervals)):
# 如果下一个元素是前一个元素的重叠区间，就加一
if start[1] > intervals[i][0]:
res += 1
# 否则更新当前元素
else:
start = intervals[i]
return res
860. 柠檬水找零
最先的想法是维护一个实时收益表，每次收钱都考虑更新这个表，尝试找到零钱，并且更新收益表。但是没有仔细看只有三个面额。
贪心的逻辑在于每次优先用大面额找零，而且要组合找。
优化后的代码如下：
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
# 记录不同面额钞票的数量
income = {5: 0, 10: 0, 20: 0}
for bill in bills:
# 收到的钱加入到收益中
income[bill] += 1
# 找零
change = bill - 5
# 尝试使用10美元找零
while change >= 10 and income[10] > 0:
income[10] -= 1
change -= 10
# 使用5美元找零
while change >= 5 and income[5] > 0:
income[5] -= 1
change -= 5
# 如果还需要找零，说明无法找零，返回False
if change > 0:
return False
return True
实际上，只需要跟踪5和10的数量即可，只关心找零是否成功
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five, ten = 0, 0 # 初始化5美元和10美元的数量
for bill in bills:
if bill == 5:
five += 1 # 收到5美元，直接增加5美元的数量
elif bill == 10:
if five == 0:
return False # 如果没有5美元找零，返回False
five -= 1 # 使用一张5美元找零
ten += 1 # 增加10美元的数量
else: # 当收到20美元时
if ten > 0 and five > 0:
ten -= 1 # 优先使用一张10美元和一张5美元找零
five -= 1
elif five >= 3:
five -= 3 # 如果没有10美元，使用三张5美元找零
else:
return False # 如果上述情况都不满足，返回False
return True # 如果能为每位顾客成功找零，返回True
135. 分发糖果
每个孩子至少一个，因此初始化一个结果数组，元素为1.
然后分别从左到右和从右到左遍历检查当前孩子和左边与右边的评分相比，决定糖果数量。
问题的关键在于每个孩子至少要分配到1个糖果，如果一个孩子的评分高于他相邻的孩子，那么这个孩子必须得到比相邻孩子更多的糖果。这个问题的复杂之处在于，单次从左到右或从右到左的扫描可能无法正确处理所有情况，因为对于任意位置的孩子，他们的糖果数取决于左右两边相邻孩子的评分。
你的代码尝试通过一个
while循环一次性解决问题，但是这种方式可能无法保证满足题目中的所有要求，尤其是当存在“峰”和“谷”的评分模式时。为了确保所有的规则都被满足，我们可以采取两次遍历的策略：
- 从左向右遍历：确保每个孩子与其左侧相邻的孩子相比较，如果评分更高，则分配的糖果数为左侧孩子的糖果数加1。
- 从右向左遍历：同理，这次确保与右侧相邻的孩子相比较，如果评分更高，则分配的糖果数为右侧孩子的糖果数加1。这时候，如果计算出的糖果数比当前已有的糖果数多，就更新当前孩子的糖果数。
通过两次遍历，我们可以确保所有的分配规则都被正确处理。下面是对应的代码实现：
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
nums = [1] * n # 初始化每个孩子至少一个糖果
# 从左向右遍历，确保每个孩子比其左侧评分高的情况
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
nums[i] = nums[i - 1] + 1
# 从右向左遍历，确保每个孩子比其右侧评分高的情况
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
nums[i] = max(nums[i], nums[i + 1] + 1)
# 计算总的糖果数
return sum(nums)
这段代码首先从左到右遍历一遍，确保每个孩子如果比左边的孩子评分高，则他会得到更多的糖果。然后从右到左再遍历一遍，这次是为了确保每个孩子如果比右边的孩子评分高，也会得到更多的糖果。两次遍历后，我们可以保证所有的分配规则都被满足。最后，返回nums数组中所有数的和，即为需要的最少糖果数。
55. 跳跃游戏
在这个问题中，我们希望知道是否能从数组的第一个位置跳到最后一个位置。使用贪婪算法，我们可以在每一步都尽可能跳得最远，这样如果能到达数组的末尾或者超过，就意味着游戏可以完成。
贪婪算法的关键在于，我们不需要在每一步都选择最优解，只需要保证能够达到最远的地方即可。我们可以维护一个变量，记录在当前和之前的所有选择中，能达到的最远位置。如果在某个位置上，这个最远位置还没到当前位置，说明我们已经无法再前进了，游戏失败。否则，只要这个最远位置到达或超过数组的最后一个位置，就意味着游戏可以完成。
以下是基于这个思路的代码实现：
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach = 0 # 初始化能到达的最远位置
for i, jump in enumerate(nums):
# 如果当前位置已经超出了之前能达到的最远位置，则游戏失败
if i > max_reach:
return False
# 更新能到达的最远位置
max_reach = max(max_reach, i + jump)
# 如果最远位置已经到达或超过数组的最后一个位置，则游戏成功
if max_reach >= len(nums) - 1:
return True
# 遍历结束，如果没有提前返回，说明最远位置没能到达数组末尾，游戏失败
return False
这个实现中，我们遍历数组中的每个元素，用max_reach变量来记录在当前元素和之前元素的选择中，能到达的最远位置。通过更新max_reach为当前最远位置和i + jump中的较大值，我们能保证max_reach始终是在当前选择下能达到的最远位置。如果在某个位置上，发现max_reach还没到当前位置，意味着我们已经无法前进，直接返回False。如果在遍历过程中max_reach到达或超过了数组的最后一个位置，就返回True。
好的，让我们使用数组
[3,2,1,0,4]作为例子，来一步步走过代码的执行过程，以便更好地理解贪婪算法在这个问题上的应用。初始状态：
max_reach = 0：最开始，我们能到达的最远位置是0，也就是数组的第一个位置。- 数组
[3,2,1,0,4]：表示在每个位置上，我们最多可以向前跳的步数。遍历数组：
- i = 0，jump = 3：
i没有超过max_reach（即0），我们可以从这个位置开始跳跃。- 更新
max_reach = max(0, 0 + 3) = 3。这意味着通过从位置0出发，我们最远能到达位置3（即数组索引为3的位置）。- i = 1，jump = 2：
- 同样，
i = 1没有超过当前的max_reach = 3。- 更新
max_reach = max(3, 1 + 2) = 3。从位置1跳2步能到达的位置（索引为3）不超过通过位置0能到达的最远位置，所以max_reach保持不变。- i = 2，jump = 1：
i = 2仍然没有超过max_reach = 3。- 更新
max_reach = max(3, 2 + 1) = 3。从位置2跳1步我们能到达的位置（索引为3）同样不超过之前的最远位置，max_reach保持不变。- i = 3，jump = 0：
- 在这里，
i = 3也没有超过max_reach = 3。- 更新
max_reach = max(3, 3 + 0) = 3。从位置3开始我们不能前进（因为jump = 0），所以max_reach依然是3。- i = 4，jump = 4：
- 现在，
i = 4已经超过了之前计算的max_reach = 3。这意味着我们无法从任何之前的位置跳到位置4，因为在我们尝试到达位置4之前，最远只能到达位置3。在这个时刻，条件if i > max_reach:被满足，函数返回False。通过这个例子，我们可以看到，即使数组的第一个元素允许我们跳得很远，但由于在索引3的位置（值为0），我们无法前进到更远的位置，导致我们无法到达数组的末尾。因此，
if i > max_reach:这个条件检查是用来确定是否存在一个位置i，在这个位置上我们已经无法基于之前的跳跃到达或者跳越，即游戏失败。
45. 跳跃游戏 II
每次都跳最远，当到了当前跳跃区间的末尾的时候，就往后跳跃，记录一次。
class Solution:
def jump(self, nums: List[int]) -> int:
jumps = 0 # 跳跃次数
current_end = 0 # 当前跳跃区间的末尾
farthest = 0 # 在当前跳跃区间内，能到达的最远位置
# 遍历数组，但不包括最后一个元素，因为到达最后一个元素时不需要再跳跃
for i in range(len(nums) - 1):
# 更新在当前跳跃区间内能到达的最远位置
farthest = max(farthest, i + nums[i])
# 如果到达了当前跳跃区间的末尾
if i == current_end:
jumps += 1 # 需要进行下一次跳跃
current_end = farthest # 更新当前跳跃区间的末尾为新的最远位置
return jumps
当然，让我们通过一个具体的例子来解释这个算法是如何工作的。假设我们有如下输入数组：
nums = [2, 3, 1, 1, 4]
我们的目标是找到从第一个元素（索引
0）跳到最后一个元素（索引4）的最少跳跃次数。
初始化：
jumps = 0，因为还没有开始跳跃。current_end = 0，当前跳跃区间的末尾初始化为第一个元素的位置。farthest = 0，当前能到达的最远位置。第一轮遍历 (
i = 0)：
- 我们从索引
0出发，可以跳2步，所以farthest = max(0, 0 + 2) = 2。- 在本轮遍历结束时，
i == current_end，表示我们到达了当前跳跃区间的末尾，需要进行一次跳跃。- 进行跳跃，
jumps = 1，更新current_end = farthest = 2。现在，我们的跳跃区间更新为索引0到索引2。第二轮遍历 (
i = 1)：
- 我们在索引
1，可以跳3步，所以farthest = max(2, 1 + 3) = 4。- 由于
i != current_end，我们继续遍历而不增加跳跃次数。第三轮遍历 (
i = 2)：
- 我们在索引
2，可以跳1步，farthest仍然是4，因为max(4, 2 + 1) = 4。- 在本轮遍历结束时，
i == current_end，表示我们到达了当前跳跃区间的末尾，需要进行一次跳跃。- 进行跳跃，
jumps = 2，更新current_end = farthest = 4。现在，我们的跳跃区间更新为索引2到索引4。由于
farthest已经达到或超过了数组的最后一个位置，我们已经找到了从起点到终点的路径，并且这个过程中一共进行了2次跳跃，所以最少跳跃次数是2。这个算法的精髓在于贪心地在每个可能的跳跃区间内选择能跳得最远的位置作为下一次的跳跃目标，从而用最少的跳跃次数到达数组的末尾。
881. 救生艇
为最小化船只数量，应该将尝试将最大的和最小的匹配；如果失败，说明最大的应该独享。
排序和双指针
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
# 让最轻和最重的人坐
people.sort()
# 指针指向最轻和最重的
left, right = 0, len(people)-1
# 船的数量
boats = 0
while left <= right:
if people[left] + people[right] <= limit:
left += 1 # 最轻的人可以跳过了
# 如果配对成功，最终的要坐，不成功说明就是独享一个船
right -= 1
# 不管是俩人，还是一人，都要坐一艘船
boats += 1
return boats