贪心算法（Greedy Algorithm）介绍

什么是贪心算法？

贪心算法是一种在每一步选择中都采取在当前看来最优的选择，从而希望得到一个全局最优解的算法。它并不从整体最优上进行考虑，而是局部最优的积累，最终形成一个可能是全局最优的结果。这种算法策略简单、高效，但并非所有问题都能通过贪心算法得到最优解。

核心思想

贪心算法的核心思想是：

贪心选择性质（Greedy Choice Property）： 问题的全局最优解可以通过一系列局部最优（即贪心）选择来达到。在每一步做出选择时，只考虑当前状态下最好的选择，而不考虑对后续步骤的影响。
最优子结构性质（Optimal Substructure）： 一个问题的最优解包含其子问题的最优解。这意味着如果一个问题能用贪心算法解决，那么它的子问题也必须能用同样的方法解决。

经典案例分析

以下通过几个经典的LeetCode问题，具体展示贪心算法的应用。

1. 分发饼干 (LeetCode 455)

问题描述：
你有一堆饼干和一群孩子，每个孩子有一个“胃口值”，每块饼干有一个“尺寸”。你希望用有限的饼干满足尽可能多的孩子，且每个满足的孩子的饼干尺寸必须大于等于其胃口值。

贪心策略：
为了满足最多的孩子，我们应该优先满足胃口最小的孩子，并用能满足他的最小饼干。

将孩子们的胃口值和饼干的尺寸都进行升序排序。
从胃口最小的孩子开始，依次尝试用最小的饼干去满足他。
如果一块饼干可以满足当前孩子，则这块饼干就分发出去，然后继续考虑下一个孩子。
如果饼干太小，则换下一块更大的饼干。

from typing import List

def findContentChildren(g: List[int], s: List[int]) -> int:
    """
    用贪心算法解决分发饼干问题。

    Args:
        g: 孩子的胃口值列表。
        s: 饼干的尺寸列表。

    Returns:
        能满足的孩子的最大数量。
    """
    g.sort()  # 排序孩子的胃口值，从小到大
    s.sort()  # 排序饼干的尺寸，从小到大

    child_idx = 0
    cookie_idx = 0
    content_children = 0

    while child_idx < len(g) and cookie_idx < len(s):
        # 如果当前饼干能满足当前孩子的胃口
        if s[cookie_idx] >= g[child_idx]:
            content_children += 1
            child_idx += 1
            cookie_idx += 1
        else:
            # 如果饼干太小，尝试下一块更大的饼干
            cookie_idx += 1

    return content_children

# 示例
g = [1, 2, 3]
s = [1, 1]
print(f"孩子们胃口: {g}, 饼干尺寸: {s}")
print(f"能满足的孩子数量: {findContentChildren(g, s)}")

g = [10, 9, 8, 7]
s = [5, 6, 7, 8]
print(f"孩子们胃口: {g}, 饼干尺寸: {s}")
print(f"能满足的孩子数量: {findContentChildren(g, s)}")

2. 无重叠区间 (LeetCode 435)

问题描述：
给定一系列区间，你需要移除最少数量的区间，使剩下的区间互不重叠。

贪心策略：
这个问题可以转化为“在所有区间中，最多能选出多少个互不重叠的区间”。

将所有区间按照结束时间进行升序排序。
从第一个区间开始，选择结束时间最早的区间。
然后，在剩下的区间中，选择第一个起始时间大于或等于已选区间结束时间的区间。
重复此过程，直到遍历完所有区间。
最终，用总区间数减去选出的不重叠区间数，即可得到需要移除的最小数量。

from typing import List

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    """
    用贪心算法解决无重叠区间问题。

    Args:
        intervals: 区间列表，每个区间为一个[起始，结束]的列表。

    Returns:
        需要移除的最小区间数量。
    """
    # 按照区间的结束时间进行升序排序
    intervals.sort(key=lambda x: x[1])

    end = float('-inf')  # 记录上一个不重叠区间的结束时间
    count = 0  # 记录不重叠区间的数量

    for interval in intervals:
        # 如果当前区间的起始时间大于等于上一个不重叠区间的结束时间，则它们不重叠
        if interval[0] >= end:
            count += 1
            end = interval[1] # 更新结束时间为当前区间的结束时间

    # 总区间数减去不重叠区间的数量，就是需要移除的最小数量
    return len(intervals) - count

# 示例
intervals1 = [[1, 2], [2, 3], [3, 4], [1, 3]]
print(f"区间列表: {intervals1}")
print(f"需要移除的最小数量: {eraseOverlapIntervals(intervals1)}")

intervals2 = [[1, 2], [1, 2], [1, 2]]
print(f"区间列表: {intervals2}")
print(f"需要移除的最小数量: {eraseOverlapIntervals(intervals2)}")

3. 柠檬水找零 (LeetCode 860)

问题描述：
你经营着一家柠檬水店，每杯柠檬水售价5美元。顾客支付的钱可能是5、10或20美元。你需要为他们正确找零。

贪心策略：
为了确保能为后面的顾客找零，我们应该优先使用面额较大的钞票进行找零，以保留小面额的钞票。

使用两个变量分别记录手头5美元和10美元钞票的数量。
当顾客支付10美元时，找零5美元（如果有的话）。
当顾客支付20美元时，找零15美元。此时，优先使用一张10美元和一张5美元。如果10美元不够，则使用三张5美元。
每收到一张5美元，5美元的计数加一。每发出找零，相应的钞票计数减一。

from typing import List

def lemonadeChange(bills: List[int]) -> bool:
    """
    用贪心算法解决柠檬水找零问题。

    Args:
        bills: 顾客支付的账单列表。

    Returns:
        如果能为所有顾客正确找零，返回True，否则返回False。
    """
    five_count = 0   # 5美元钞票的数量
    ten_count = 0    # 10美元钞票的数量

    for bill in bills:
        if bill == 5:
            # 收到5美元，直接增加计数
            five_count += 1
        elif bill == 10:
            # 收到10美元，需要找零5美元
            if five_count > 0:
                five_count -= 1
                ten_count += 1
            else:
                return False
        elif bill == 20:
            # 收到20美元，需要找零15美元
            if ten_count > 0 and five_count > 0:
                # 优先找一张10美元和一张5美元
                ten_count -= 1
                five_count -= 1
            elif five_count >= 3:
                # 如果没有10美元，则用三张5美元
                five_count -= 3
            else:
                return False
    return True

# 示例
bills1 = [5, 5, 5, 10, 20]
print(f"账单列表: {bills1}")
print(f"是否能正确找零: {lemonadeChange(bills1)}")

bills2 = [5, 5, 10, 10, 20]
print(f"账单列表: {bills2}")
print(f"是否能正确找零: {lemonadeChange(bills2)}")

总结

贪心算法是一种直观且易于实现的算法，适用于满足贪心选择性质和最优子结构性质的问题。它的优势在于简单和高效，但缺点也很明显，即它无法保证在所有问题上都能找到全局最优解。因此，在应用贪心算法之前，需要仔细分析问题，确保其满足上述两个关键性质。