用Python实战图解贪心算法：从LeetCode经典题解到避坑指南

第一次接触贪心算法时，我盯着"局部最优导致全局最优"的定义发呆了半小时——这听起来像在描述某种玄学。直到在LeetCode周赛中被一道简单题卡住两小时后才明白：理解贪心算法的关键在于 可视化决策过程 。本文将用Python带你看清贪心策略的内在逻辑，通过五个经典问题揭示其精妙之处与致命陷阱。

1. 贪心算法核心：决策时刻的可视化

贪心算法不是魔法，它的有效性建立在两个可验证的数学性质上：贪心选择性质与最优子结构。但初学者最需要的是 直观感受决策过程 。让我们用找零问题为例：

def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)  # 从大到小排序
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
            print(f"选择{coin}元硬币 | 剩余金额:{amount}")
    return count if amount == 0 else -1

print(coin_change_greedy([1, 5, 10], 27))

执行这段代码时，控制台会打印：

选择10元硬币 | 剩余金额:17
选择10元硬币 | 剩余金额:7
选择5元硬币 | 剩余金额:2
选择1元硬币 | 剩余金额:1
选择1元硬币 | 剩余金额:0

关键观察：每次选择都 立即减少问题规模 ，且后续选择不会推翻前面的决定。这就是贪心选择性质的直观体现。

但这种方法对硬币体系[4,3,1]和目标金额6就会失效：

选择4元硬币 | 剩余金额:2
选择1元硬币 | 剩余金额:1
选择1元硬币 | 剩余金额:0  # 实际最优解是两个3元硬币

2. LeetCode经典问题实战

2.1 区间调度问题（LeetCode 435）

这是理解贪心策略的绝佳案例。给定一组区间，计算需要移除的最小区间数使剩余区间互不重叠：

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])  # 按结束时间排序
    end = float('-inf')
    count = 0
    for interval in intervals:
        if interval[0] >= end:  # 无重叠
            end = interval[1]
            count += 1
    return len(intervals) - count

决策可视化技巧 ：在纸上画出排序后的区间，用不同颜色标记选中的区间。你会发现：

• 每次选择 最早结束 的区间，能给后续留下更多选择空间
• 这种局部选择最终导致全局最优解

2.2 加油站问题（LeetCode 134）

这个问题完美展示了贪心算法的反直觉特性：

def can_complete_circuit(gas, cost):
    total_tank = curr_tank = start = 0
    for i in range(len(gas)):
        total_tank += gas[i] - cost[i]
        curr_tank += gas[i] - cost[i]
        if curr_tank < 0:  # 无法到达下一站
            start = i + 1
            curr_tank = 0
    return start if total_tank >= 0 else -1

关键突破点：如果从站A出发无法到达站B，那么A-B之间的任何站都不能作为起点。这个观察将时间复杂度从O(n²)降到O(n)。

3. 贪心算法的典型陷阱

3.1 局部最优≠全局最优

背包问题是最著名的反例。考虑物品：

• 物品1：价值60，重量10（单位价值6）
• 物品2：价值100，重量20（单位价值5）
• 物品3：价值120，重量30（单位价值4）

背包容量50时，贪心算法会选择物品1+物品2（总价值160），而最优解是物品2+物品3（总价值220）。

3.2 证明方法实战

验证贪心策略有效性的两种实用方法：

1. 交换论证 ：假设存在更优解，尝试用贪心选择的元素替换其中的元素而不破坏最优性
2. 归纳法 ：证明第一步选择正确，且后续步骤保持最优性

以区间调度问题为例的归纳证明：

• 基础情况：选择最早结束的区间是正确的
• 归纳步骤：剩余子问题的最优解加上第一个选择仍是全局最优

4. 贪心算法的特殊变体

4.1 拟阵理论应用

某些问题结构天然适合贪心算法。拟阵的典型例子是Kruskal算法求最小生成树：

def kruskal(n, edges):
    parent = [i for i in range(n)]
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    
    edges.sort(key=lambda x: x[2])
    mst = []
    for u, v, w in edges:
        if find(u) != find(v):
            mst.append((u, v, w))
            parent[find(u)] = find(v)
    return mst

4.2 带反悔的贪心

某些问题需要"暂时接受非最优选择"：

import heapq

def max_capital(k, W, profits, capital):
    min_heap = []
    max_heap = []
    for i in range(len(capital)):
        heapq.heappush(min_heap, (capital[i], profits[i]))
    
    for _ in range(k):
        while min_heap and min_heap[0][0] <= W:
            c, p = heapq.heappop(min_heap)
            heapq.heappush(max_heap, -p)
        if not max_heap:
            break
        W += -heapq.heappop(max_heap)
    return W

5. 面试实战技巧

在技术面试中处理贪心算法问题时：

1. 快速验证三步法 ：

   • 尝试举出反例
   • 检查问题是否具有最优子结构
   • 验证贪心选择性质

2. 代码模板 ：

def greedy_solution(inputs):
    # 预处理（通常需要排序）
    inputs.sort(key=...)  
    
    result = 0
    current_state = initial_value
    for item in inputs:
        if meets_condition(current_state, item):
            update(current_state, item)
            result += 1  # 或其他度量
    return result

3. 常见问题模式识别 ：
   • 区间类问题 → 通常按结束时间排序
   • 分配类问题 → 双指针或双堆
   • 字符串构造 → 频率统计+贪心选择

记得在LeetCode练习时，特别关注这些标签下的题目：

• 简单：455（分发饼干）、860（柠檬水找零）
• 中等：376（摆动序列）、738（单调递增数字）
• 困难：502（IPO）、630（课程表III）