第13章：贪心算法的正确性

贪心算法是一种看似简单却极具技巧性的算法思想。对于资深工程师而言，难点不在于实现贪心策略，而在于如何证明贪心选择的正确性，以及识别何时贪心策略会失效。本章将深入探讨贪心算法的数学本质，帮助你建立严谨的贪心思维框架。

13.1 贪心选择性质的证明

13.1.1 贪心算法的本质

贪心算法的核心思想是：每一步都做出局部最优选择，期望最终得到全局最优解。这种策略之所以有效，依赖于问题满足两个关键性质：

贪心选择性质（Greedy Choice Property）：局部最优选择能导向全局最优解
最优子结构（Optimal Substructure）：问题的最优解包含子问题的最优解

让我们通过经典的跳跃游戏来理解这个概念。

13.1.2 跳跃游戏 I (#55)

def canJump(nums):
    """
    思路：维护能够到达的最远位置
    贪心选择：在可达范围内，选择能跳得最远的位置
    """
    max_reach = 0
    n = len(nums)

    for i in range(n):
        if i > max_reach:  # 当前位置不可达
            return False
        max_reach = max(max_reach, i + nums[i])
        if max_reach >= n - 1:  # 提前返回
            return True

    return True

正确性证明：

归纳基础：从位置0开始，max_reach = nums[0]
归纳假设：对于位置i，max_reach表示从0到i所有位置能够到达的最远位置
归纳步骤：如果i+1 ≤ max_reach，则i+1可达，更新max_reach = max(max_reach, i+1+nums[i+1])
结论：如果存在到达末尾的路径，贪心策略一定能找到

13.1.3 跳跃游戏 II (#45)

def jump(nums):
    """
    思路：BFS层序遍历的贪心实现
    每一"层"表示用相同步数能到达的位置范围
    """
    n = len(nums)
    if n <= 1:
        return 0

    jumps = 0
    current_end = 0  # 当前层的右边界
    farthest = 0     # 下一层能到达的最远位置

    for i in range(n - 1):  # 注意不需要访问最后一个位置
        farthest = max(farthest, i + nums[i])

        if i == current_end:  # 到达当前层的边界
            jumps += 1
            current_end = farthest

            if current_end >= n - 1:
                break

    return jumps

关键洞察：

这个问题本质上是在求最短路径（最少跳跃次数）
贪心策略等价于BFS，每次扩展都选择能到达最远的位置
时间复杂度O(n)，比显式BFS的O(n²)更优

13.1.4 贪心证明的一般框架

证明贪心算法正确性的常用方法：

交换论证（Exchange Argument） - 假设存在最优解OPT不包含贪心选择 - 通过交换操作将贪心选择加入OPT - 证明交换后的解不会变差
反证法（Contradiction） - 假设贪心解不是最优的 - 推导出矛盾
归纳法（Induction） - 证明每一步的贪心选择都保持最优性

13.2 区间调度与活动选择

区间调度问题是贪心算法的经典应用场景。这类问题的关键在于如何定义"贪心标准"：是按开始时间、结束时间、还是区间长度？

13.2.1 无重叠区间 (#435)

给定一个区间集合，找到需要移除的最少区间数，使得剩余区间互不重叠。

def eraseOverlapIntervals(intervals):
    """
    贪心策略：保留结束时间最早的区间
    这样给后续区间留下最大空间
    """
    if not intervals:
        return 0

    # 按结束时间排序
    intervals.sort(key=lambda x: x[1])

    count = 0  # 需要移除的区间数
    prev_end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] < prev_end:  # 有重叠
            count += 1
        else:
            prev_end = intervals[i][1]

    return count

正确性证明（交换论证）：

假设最优解OPT选择了区间A而非贪心选择的区间B（B的结束时间更早）
将OPT中的A替换为B，由于B结束更早，不会与OPT中其他区间产生新的冲突
因此替换后的解至少和OPT一样好，证明贪心选择正确

13.2.2 用最少数量的箭引爆气球 (#452)

def findMinArrowShots(points):
    """
    思路：将问题转化为最多不重叠区间数
    每个不重叠的区间组至少需要一支箭
    """
    if not points:
        return 0

    # 按结束位置排序
    points.sort(key=lambda x: x[1])

    arrows = 1
    prev_end = points[0][1]

    for i in range(1, len(points)):
        if points[i][0] > prev_end:  # 没有重叠，需要新的箭
            arrows += 1
            prev_end = points[i][1]
        # 如果有重叠，当前箭可以射穿两个气球

    return arrows

13.2.3 会议室 II (#253)

给定会议时间安排，求需要的最少会议室数量。

def minMeetingRooms(intervals):
    """
    方法1：扫描线算法
    将开始和结束时间分别处理
    """
    starts = sorted([i[0] for i in intervals])
    ends = sorted([i[1] for i in intervals])

    rooms = 0
    max_rooms = 0
    s = e = 0

    while s < len(starts):
        if starts[s] < ends[e]:
            rooms += 1  # 新会议开始，需要新房间
            max_rooms = max(max_rooms, rooms)
            s += 1
        else:
            rooms -= 1  # 有会议结束，释放房间
            e += 1

    return max_rooms

def minMeetingRooms_heap(intervals):
    """
    方法2：最小堆维护结束时间
    堆的大小就是需要的会议室数
    """
    import heapq

    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[0])  # 按开始时间排序

    heap = []  # 存储会议结束时间
    heapq.heappush(heap, intervals[0][1])

    for i in range(1, len(intervals)):
        if intervals[i][0] >= heap[0]:  # 可以复用最早结束的会议室
            heapq.heappop(heap)
        heapq.heappush(heap, intervals[i][1])

    return len(heap)

13.2.4 区间问题的贪心策略总结

| 问题类型 | 贪心策略 | 排序关键字 |

问题类型	贪心策略	排序关键字
最多不重叠区间	选择结束最早的	结束时间
区间覆盖	选择覆盖最远的	开始时间
区间分组	扫描线或堆	开始时间
区间合并	排序后线性扫描	开始时间

13.3 哈夫曼编码与最优合并

哈夫曼编码展示了贪心算法在构造最优二叉树中的应用。核心思想是：频率越高的字符，编码越短。

13.3.1 连接木棍的最低费用 (#1167)

给定n根木棍，每次连接两根的费用为它们长度之和。求将所有木棍连成一根的最小费用。

def connectSticks(sticks):
    """
    贪心策略：每次选择最短的两根木棍连接
    这是经典的哈夫曼树构造问题
    """
    import heapq

    if len(sticks) <= 1:
        return 0

    heapq.heapify(sticks)  # 转换为最小堆
    total_cost = 0

    while len(sticks) > 1:
        # 取出最短的两根
        first = heapq.heappop(sticks)
        second = heapq.heappop(sticks)

        # 连接费用
        cost = first + second
        total_cost += cost

        # 将新木棍放回堆中
        heapq.heappush(sticks, cost)

    return total_cost

数学证明：设木棍长度为 $w_1, w_2, ..., w_n$，在哈夫曼树中，每个叶节点的深度为 $d_i$。总费用 = $\sum_{i=1}^{n} w_i \cdot d_i$

贪心选择保证了权重最小的节点深度最大，这正是哈夫曼编码的最优性质。

13.3.2 任务调度器 (#621)

给定一组任务和冷却时间n，相同任务之间必须间隔至少n个时间单位。求完成所有任务的最短时间。

def leastInterval(tasks, n):
    """
    关键洞察：最频繁的任务决定了总时间的下界
    """
    from collections import Counter

    # 统计任务频率
    freq = Counter(tasks)
    max_freq = max(freq.values())

    # 计算有多少任务具有最大频率
    max_count = sum(1 for f in freq.values() if f == max_freq)

    # 情况1：由最频繁任务决定
    # (max_freq - 1) * (n + 1) + max_count
    # 
    # 情况2：任务足够多，不需要空闲时间
    # len(tasks)

    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

可视化理解：

任务: A A A B B B C C D E, n = 2
频率: A:3, B:3, C:2, D:1, E:1

构造方式（按列填充）：
A B C
A B C
A B D E

总时间 = 10

13.3.3 最优合并的一般模式

最优合并问题的共同特征：

每次合并的代价与参与合并的元素相关
目标是最小化总合并代价
贪心策略：优先合并代价最小的元素

def optimalMerge(elements, merge_cost_func):
    """
    通用的最优合并框架
    """
    import heapq

    heap = elements.copy()
    heapq.heapify(heap)
    total_cost = 0

    while len(heap) > 1:
        # 选择代价最小的两个元素
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)

        # 计算合并代价
        cost = merge_cost_func(a, b)
        total_cost += cost

        # 将合并结果放回
        heapq.heappush(heap, a + b)  # 或其他合并方式

    return total_cost

13.4 贪心的反例与陷阱

并非所有看似贪心的问题都能用贪心解决。理解贪心算法的局限性同样重要。

13.4.1 根据身高重建队列 (#406)

给定一组人的身高和前面有多少人更高的信息，重建队列。

def reconstructQueue(people):
    """
    贪心策略：先排高的人，再插入矮的人
    关键洞察：矮的人不会影响高的人的k值
    """
    # 按身高降序、k值升序排序
    people.sort(key=lambda x: (-x[0], x[1]))

    result = []
    for person in people:
        # 在位置k插入当前人
        # 因为已经有k个更高的人在前面
        result.insert(person[1], person)

    return result

为什么这个贪心策略有效？

高个子先站好位置后，矮个子插入不会影响高个子的相对位置
每个人插入时，前面恰好有k个比他高的人
这种顺序保证了局部决策的独立性

13.4.2 贪心失效的经典例子

背包问题（不能用贪心）

def knapsack_greedy_wrong(items, capacity):
    """
    错误的贪心策略：按单位价值排序
    反例：
    items = [(weight=10, value=10), (weight=20, value=20), (weight=15, value=30)]
    capacity = 30
    贪心选择：item[2] + item[0] = 40
    最优解：item[1] + item[0] = 30
    """
    # 这是错误的方法！
    items.sort(key=lambda x: x[1]/x[0], reverse=True)
    # ... 贪心选择会导致次优解

最短路径（Dijkstra有条件限制）

def dijkstra_negative_edge_wrong(graph):
    """
    Dijkstra算法在有负权边时失效
    原因：贪心选择的"最短"可能通过负权边变得更短

    反例图：
    A --1--> B
    |        |
    10      -20
    |        |
    v        v
    C <------D

    从A到C：贪心选择A->C (10)
    实际最短：A->B->D->C (-8)
    """
    pass

13.4.3 判断是否能用贪心的技巧

检查贪心选择性质 - 问问自己：做出局部最优选择后，剩余问题是否仍是原问题的子问题？ - 能否证明局部最优导向全局最优？
寻找反例 - 构造小规模测试用例 - 特别关注边界情况
与动态规划对比 - 如果需要考虑多个之前的状态，通常不能用贪心 - 如果决策依赖于未来的选择，通常不能用贪心

13.4.4 常见的贪心陷阱

class GreedyPitfalls:
    """
    总结常见的贪心算法陷阱
    """

    @staticmethod
    def trap1_local_not_global():
        """
        陷阱1：局部最优不等于全局最优
        例子：硬币找零问题
        """
        def coinChange_greedy_wrong(coins, amount):
            # 贪心：每次选最大面值
            # 反例：coins=[1,3,4], amount=6
            # 贪心：4+1+1=3枚
            # 最优：3+3=2枚
            pass

    @staticmethod
    def trap2_order_matters():
        """
        陷阱2：处理顺序影响结果
        例子：任务调度问题中的顺序选择
        """
        pass

    @staticmethod  
    def trap3_hidden_constraints():
        """
        陷阱3：隐含的约束条件
        例子：会议室分配中的时间冲突
        """
        pass

本章小结

贪心算法的优雅在于其简洁性，挑战在于正确性证明。作为资深工程师，你应该：

掌握证明技巧 - 交换论证：证明贪心选择至少和最优解一样好 - 归纳法：证明每步贪心选择都保持最优性 - 反证法：假设非贪心解更优，推出矛盾
识别问题模式 - 区间调度：结束时间优先 - 最优合并：哈夫曼树构造 - 活动选择：不重叠区间最大化
理解算法本质 - 贪心vs动态规划：无后效性vs有后效性 - 局部最优vs全局最优：需要严格证明 - 问题建模：将实际问题转化为已知模式
关键公式总结 - 区间调度：按结束时间排序，$O(n\log n)$ - 哈夫曼编码：总代价 = $\sum w_i \cdot d_i$ - 任务调度：时间 = $\max(\text{任务总数}, (\text{最大频率}-1) \times (n+1) + \text{最大频率任务数})$

常见陷阱与错误 (Gotchas)

1. 贪心选择的正确性陷阱

错误：凭直觉选择贪心策略，不加证明

# 错误示例：硬币找零
def coinChange_wrong(coins, amount):
    # 直觉：每次选最大面值
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count if amount == 0 else -1
    # 反例：coins=[1,3,4], amount=6

正确做法：先尝试构造反例，再决定是否用贪心

2. 排序关键字选择错误

错误：区间问题随意选择排序标准

# 错误：按开始时间排序选择不重叠区间
intervals.sort(key=lambda x: x[0])  # 应该按结束时间

记忆技巧：

最多不重叠 → 结束时间（给后续留空间）
区间覆盖 → 开始时间（覆盖更远）
区间合并 → 开始时间（方便遍历）

3. 边界条件处理

常见错误：

# 错误：跳跃游戏II中遍历到最后一个元素
for i in range(n):  # 应该是 range(n-1)
    # ...

调试技巧：

手动模拟小规模输入
特别关注空输入、单元素、两元素的情况
检查循环边界和数组访问

4. 优先队列使用错误

错误：忘记Python的heapq是最小堆

# 需要最大堆时的处理
import heapq
# 方法1：取负数
heapq.heappush(heap, -value)
max_value = -heapq.heappop(heap)

# 方法2：自定义比较（更复杂情况）
heap = [(-value, item) for value, item in items]
heapq.heapify(heap)

5. 贪心与DP的混淆

判断准则：

需要记录多个状态 → 用DP
决策依赖未来 → 用DP
只需局部最优 → 可能用贪心
有明显的选择顺序 → 可能用贪心

6. 复杂度分析错误

常见误区：

# 看似O(n)，实际O(n²)
for person in people:
    result.insert(person[1], person)  # insert是O(n)

优化思路：

用堆代替排序后的线性搜索
用双端队列优化插入操作
预处理减少重复计算

记住：贪心算法的美在于简洁，但正确性需要严格证明。在面试中，先说明贪心策略，再简要说明为什么有效，会让你的解答更有说服力。