贪心：局部最优的赌注
第二十六章：贪心 — 局部最优的赌注
你在一个加油站环形公路上，油箱空空如也。每个加油站能加的油和到下一站的耗油量不同。你能不能绕一圈回到起点？如果能，应该从哪个站出发？
这就是 LeetCode #134（加油站）的设定。一个直觉性的做法是：从某个站出发，如果油箱在某处变负了，说明从这个站到变负的那个站之间的任何站出发都不行——直接跳到下一个站重新开始。这个"跳过中间所有站"的决策看似鲁莽，但它是正确的。这就是贪心算法的精髓：做出局部最优的选择，赌它能导向全局最优。
贪心算法（Greedy Algorithm）是一种在每一步都选择当前看起来最好的选项的策略。它不像动态规划那样考虑所有子问题的组合，也不像回溯那样尝试所有可能性——它只看眼前，做出决定，永不回头。
这种"短视"的策略为什么有时能得到最优解？答案是：当问题具有贪心选择性质（greedy-choice property）和最优子结构（optimal substructure）时，贪心就是正确的。但问题的另一面是：当这两个性质不满足时，贪心会得到错误答案，而且它的错误往往很隐蔽——代码能跑，结果看起来合理，但就是不是最优解。
贪心的历史可以追溯到图论的早期。1930 年代 Kruskal 和 Prim 为最小生成树设计的算法就是贪心的典范（我们在第 18 章已经详细讨论）。1952 年 David Huffman 在 MIT 读研究生时发明的 Huffman 编码，开创了信息论中贪心方法的先河。今天，gzip、JPEG、MP3 这些无处不在的压缩格式都直接或间接地依赖 Huffman 编码。
这一章我们从贪心的核心思想和正确性证明出发，通过经典问题（活动选择、区间调度、Huffman 编码、背包问题）建立对贪心的深度理解，最后给出"什么时候用贪心、什么时候用 DP"的决策框架。
Level 1 · 你需要知道的
26.1 贪心的核心思想
26.1.1 什么是贪心
贪心算法的定义可以用一句话概括：
在每一步做出局部最优选择，希望这些局部最优选择能组合成全局最优解。
关键特征：
- 不回头：一旦做出选择，不会撤销
- 不考虑未来：只根据当前信息做决定
- 没有子问题组合：不像 DP 那样合并子问题的解
贪心是最"简单"的算法范式——实现通常很短，时间复杂度通常很优。难点在于：判断贪心策略是否正确。
26.1.2 贪心 vs 动态规划 vs 回溯
考虑所有可能性？ 利用子问题重叠？ 做出不可逆选择？
回溯/暴力： 是 否 否（会回退）
动态规划： 是（隐式地） 是 否
贪心： 否 不需要 是
一个直觉：
- 贪心：一条路走到黑，永不回头
- DP：每个岔路口都探索，记住最优的
- 回溯：每条路都试试，走不通就回来
26.2 活动选择问题
26.2.1 问题定义
给定 n 个活动，每个活动有开始时间 s[i] 和结束时间 f[i]。一个人同一时间只能参加一个活动。问：最多能参加多少个不重叠的活动？
这是贪心最经典的入门问题，也叫"区间调度问题"（Interval Scheduling）。
26.2.2 贪心策略：按结束时间排序
直觉：每次选择结束时间最早的活动。为什么？因为一个活动越早结束，留给后续活动的时间就越多。
def activity_selection(activities):
"""
活动选择问题：贪心法
activities: [(start, end), ...]
返回最大不重叠活动集合
"""
# 按结束时间排序
sorted_acts = sorted(activities, key=lambda x: x[1])
selected = [sorted_acts[0]]
last_end = sorted_acts[0][1]
for start, end in sorted_acts[1:]:
if start >= last_end: # 不重叠
selected.append((start, end))
last_end = end
return selected
# 示例
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
(6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
result = activity_selection(activities)
print(f"最多参加 {len(result)} 个活动: {result}")
# 最多参加 4 个活动: [(1, 4), (5, 7), (8, 11), (12, 16)]
时间复杂度： O(n log n)（排序） + O(n)（遍历） = O(n log n)
26.2.3 为什么其他贪心策略不行？
- 按开始时间排序，选最早开始的？ 错！一个活动可能从凌晨开始到深夜结束，占满整天。
- 按持续时间排序，选最短的？ 错！短活动可能恰好卡在两个长活动之间，选了它反而排斥了两个。
- 按冲突数排序，选冲突最少的？ 看似合理，但复杂度高且可以构造反例。
只有"结束时间最早"这个策略是正确的。为什么？我们在 Level 2 中严格证明。
26.3 区间调度问题
区间调度是活动选择的泛化。常见的三种变体：
26.3.1 最大不重叠区间数（等价于活动选择）
def max_non_overlapping(intervals):
"""LeetCode #435 的逆问题：最大不重叠区间数"""
if not intervals:
return 0
intervals.sort(key=lambda x: x[1])
count = 1
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end:
count += 1
last_end = end
return count
26.3.2 最少移除使区间不重叠（LeetCode #435）
def erase_overlap_intervals(intervals):
"""
LeetCode #435: 无重叠区间
返回最少需要移除的区间数，使剩余区间互不重叠
"""
if not intervals:
return 0
# 贪心策略：最大不重叠 = 总数 - 需要移除的
max_keep = max_non_overlapping(intervals)
return len(intervals) - max_keep
# 示例
intervals = [[1,2],[2,3],[3,4],[1,3]]
print(erase_overlap_intervals(intervals)) # 1（移除[1,3]）
26.3.3 最少箭引爆气球（LeetCode #452）
def find_min_arrow_shots(points):
"""
LeetCode #452: 用最少数量的箭引爆气球
每个 point 是气球的水平区间 [x_start, x_end]
一支箭可以引爆所有包含该 x 坐标的气球
"""
if not points:
return 0
# 按右端点排序
points.sort(key=lambda x: x[1])
arrows = 1
arrow_pos = points[0][1] # 箭射在第一个气球的右端点
for start, end in points[1:]:
if start > arrow_pos: # 当前气球不被之前的箭覆盖
arrows += 1
arrow_pos = end
return arrows
# 示例
points = [[10,16],[2,8],[1,6],[7,12]]
print(find_min_arrow_shots(points)) # 2
关键洞察： 这三个问题的核心都是"按右端点排序 + 贪心选择"。它们看起来不同，但数学本质相同。
26.4 跳跃游戏
26.4.1 LeetCode #55: 跳跃游戏（能否到达终点）
给定数组 nums，nums[i] 表示从位置 i 最多能跳 nums[i] 步。判断能否到达最后一个位置。
def can_jump(nums):
"""
LeetCode #55: 跳跃游戏
贪心：维护能到达的最远位置
"""
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False # 当前位置超出了能到达的范围
max_reach = max(max_reach, i + nums[i])
if max_reach >= len(nums) - 1:
return True
return True
# 示例
print(can_jump([2, 3, 1, 1, 4])) # True
print(can_jump([3, 2, 1, 0, 4])) # False
26.4.2 LeetCode #45: 跳跃游戏 II（最少跳几次）
def jump(nums):
"""
LeetCode #45: 跳跃游戏 II
贪心：在每一步的可达范围内，选择能跳最远的位置
"""
if len(nums) <= 1:
return 0
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
if current_end >= len(nums) - 1:
break
return jumps
# 示例
print(jump([2, 3, 1, 1, 4])) # 2 (0→1→4)
贪心策略解释： 把数组想象成一个个"台阶"。从位置 0 开始，你能跳到的范围是 [1, nums[0]]。在这个范围内，找到能让你跳得最远的位置——那就是下一步应该跳到的地方。这就像 BFS 的层级扩展：每一"跳"对应 BFS 的一层。
26.5 贪心的常见模式总结
| 模式 | 排序依据 | 贪心选择 | 典型问题 |
|---|---|---|---|
| 区间调度 | 右端点 | 选最早结束的 | 活动选择、#435、#452 |
| 区间覆盖 | 左端点 | 选覆盖范围最大的 | 跳跃游戏、区间覆盖 |
| 分配匹配 | 双方排序 | 最小满足最小 | 分发饼干#455 |
| 拓扑贪心 | 依赖关系 | 选入度为0的 | 任务调度 |
| 反悔贪心 | 优先队列 | 选当前最优，可反悔 | 超级丑数、IPO |
Level 2 · 它是怎么运行的
26.6 贪心正确性证明
贪心算法最大的难点不是实现，而是证明正确性。两种经典证明方法：
26.6.1 交换论证（Exchange Argument）
思路：假设存在一个最优解 OPT 不同于贪心解 G。证明可以把 OPT 中的某个选择"交换"为贪心的选择，得到的解不会更差。反复交换后，OPT 被变换为 G，说明 G 也是最优的。
活动选择问题的证明：
设贪心算法选择的活动序列为 G = {g₁, g₂, ..., gₖ}（按结束时间排序）。 设任意最优解为 OPT = {o₁, o₂, ..., oₘ}（按结束时间排序）。
我们要证明 k = m（即贪心选的数量和最优解一样多）。
Step 1: 证明 f(g₁) ≤ f(o₁)（贪心的第一个活动结束不比最优解的晚）
- 贪心选择结束最早的活动，所以 f(g₁) ≤ f(o₁)
Step 2: 用 g₁ 替换 o₁ 得到 OPT' = {g₁, o₂, ..., oₘ}
- 因为 f(g₁) ≤ f(o₁)，而 o₂ 与 o₁ 不重叠（s(o₂) ≥ f(o₁)）
- 所以 s(o₂) ≥ f(o₁) ≥ f(g₁)，即 g₁ 与 o₂ 也不重叠
- OPT' 仍然是合法解，且 |OPT'| = |OPT| = m
Step 3: 对 OPT' 的剩余活动 {o₂, ..., oₘ} 递归应用同样的论证
- 子问题：在 g₁ 结束后选择最多的不重叠活动
- 贪心在子问题上也选结束最早的（g₂）
- 同理可以替换 o₂ 为 g₂...
Step 4: 归纳得 k ≥ m。又因为 OPT 是最优解（m 最大），所以 k ≤ m。故 k = m。
def prove_greedy_optimal():
"""
交换论证的形式化（伪代码）
"""
# 假设 OPT ≠ G
# 找到第一个不同的位置 j: o_j ≠ g_j
# 因为 f(g_j) ≤ f(o_j)（贪心总是选结束最早的）
# 构造 OPT' = OPT 中 o_j 换成 g_j
# OPT' 仍合法且大小不变
# 重复直到 OPT' = G
# 结论：|G| = |OPT|
pass
26.6.2 反证法（Proof by Contradiction）
思路：假设贪心解不是最优的，推出矛盾。
跳跃游戏 II (#45) 的证明：
设贪心解跳了 k 次，设存在更优解跳了 j < k 次。
贪心算法的性质：在第 t 跳时，它的跳跃范围 [current_end_t] 是所有 t 跳方案能达到的最远位置。
证明（归纳法）：
- 第 1 跳后，贪心能到的最远位置 ≥ 任何其他方案第 1 跳后能到的位置（因为贪心在可达范围内选了能跳最远的）
- 假设第 t 跳后贪心到的位置 ≥ 其他方案第 t 跳后的位置（归纳假设）
- 第 t+1 跳：贪心从更远的位置出发，可达范围更大，所以第 t+1 跳后仍然 ≥ 其他方案
如果更优解在 j 跳后到达终点，而贪心在每一步都到得更远（或一样远），那贪心在 j 步也一定到达了终点。这与"贪心需要 k > j 步"矛盾。
26.7 Huffman 编码
26.7.1 问题背景
假设你要压缩一个只含 a、b、c、d、e 五种字符的文件。如果用固定长度编码：
- 5 个字符需要 3 bits（⌈log₂5⌉ = 3）
- 100 个字符需要 300 bits
但如果字符出现频率不同呢？比如 a 出现 45 次，b 出现 13 次，c 出现 12 次，d 出现 16 次，e 出现 9 次，f 出现 5 次。
如果给高频字符短编码、低频字符长编码，总 bits 数可以更少。这就是 Huffman 编码 的核心思想——一种前缀码（prefix-free code），保证任何字符的编码不是另一个字符编码的前缀，从而可以唯一解码。
26.7.2 Huffman 算法
贪心策略：每次合并频率最低的两个节点。
import heapq
from collections import Counter
class HuffmanNode:
"""Huffman 树节点"""
def __init__(self, char=None, freq=0, left=None, right=None):
self.char = char
self.freq = freq
self.left = left
self.right = right
def __lt__(self, other):
return self.freq < other.freq # 用于堆排序
def build_huffman_tree(text):
"""
构建 Huffman 树
贪心策略：每次合并频率最低的两个节点
"""
# 统计字符频率
freq = Counter(text)
if len(freq) == 0:
return None
if len(freq) == 1:
char = list(freq.keys())[0]
return HuffmanNode(char=char, freq=freq[char])
# 创建最小堆
heap = [HuffmanNode(char=c, freq=f) for c, f in freq.items()]
heapq.heapify(heap)
# 贪心合并
while len(heap) > 1:
# 取出频率最低的两个
left = heapq.heappop(heap)
right = heapq.heappop(heap)
# 合并为新节点
merged = HuffmanNode(
freq=left.freq + right.freq,
left=left,
right=right
)
heapq.heappush(heap, merged)
return heap[0] # 根节点
def generate_codes(root):
"""从 Huffman 树生成编码表"""
codes = {}
def traverse(node, code):
if node is None:
return
if node.char is not None: # 叶子节点
codes[node.char] = code if code else '0'
return
traverse(node.left, code + '0')
traverse(node.right, code + '1')
traverse(root, '')
return codes
def huffman_encode(text):
"""Huffman 编码"""
tree = build_huffman_tree(text)
codes = generate_codes(tree)
encoded = ''.join(codes[c] for c in text)
return encoded, codes, tree
def huffman_decode(encoded, tree):
"""Huffman 解码"""
decoded = []
node = tree
for bit in encoded:
if bit == '0':
node = node.left
else:
node = node.right
if node.char is not None: # 到达叶子
decoded.append(node.char)
node = tree # 回到根
return ''.join(decoded)
# 完整示例
text = "aaaaaaaaaaaaaabbbbbbbbbbcccccccccddddddddddddeeeeeffff"
encoded, codes, tree = huffman_encode(text)
print("字符编码表:")
for char, code in sorted(codes.items()):
print(f" '{char}': {code}")
print(f"\n原始文本长度: {len(text)} 字符")
print(f"固定编码: {len(text) * 3} bits (3 bits/char)")
print(f"Huffman 编码: {len(encoded)} bits")
print(f"压缩率: {len(encoded) / (len(text) * 8) * 100:.1f}%")
# 验证解码正确性
decoded = huffman_decode(encoded, tree)
assert decoded == text, "解码错误！"
print(f"解码验证: {'通过' if decoded == text else '失败'}")
输出示例：
字符编码表:
'a': 0
'b': 110
'c': 101
'd': 10
'e': 1110
'f': 1111
原始文本长度: 53 字符
固定编码: 159 bits (3 bits/char)
Huffman 编码: 116 bits
压缩率: 27.4%
26.7.3 Huffman 编码与 gzip 的关系
gzip 的压缩流程：
- LZ77：用滑动窗口找重复字符串，替换为（距离, 长度）对
- Huffman 编码：对 LZ77 的输出进行 Huffman 编码
gzip 实际使用两种 Huffman 编码模式：
- 静态 Huffman：使用预定义的编码表（RFC 1951 规定）
- 动态 Huffman：根据当前数据块构建最优编码表（编码表存储在压缩数据中）
# gzip 的 Deflate 算法核心流程（简化）
def deflate_simplified(data):
"""
模拟 gzip 的 Deflate 压缩（极简版）
"""
# Step 1: LZ77 — 找重复，生成 (literal/length, distance) 序列
lz77_output = lz77_compress(data)
# Step 2: Huffman — 对 LZ77 输出进行编码
# 分别为 literal/length 和 distance 各建一棵 Huffman 树
huffman_encoded = huffman_encode_lz77(lz77_output)
return huffman_encoded
def lz77_compress(data, window_size=32768, lookahead_size=258):
"""LZ77 压缩（简化版）"""
output = []
i = 0
while i < len(data):
best_length = 0
best_distance = 0
# 在滑动窗口中找最长匹配
search_start = max(0, i - window_size)
for j in range(search_start, i):
length = 0
while (i + length < len(data) and
length < lookahead_size and
data[j + length] == data[i + length]):
length += 1
if length > best_length:
best_length = length
best_distance = i - j
if best_length >= 3: # 匹配长度 >= 3 才值得用引用
output.append(('match', best_distance, best_length))
i += best_length
else:
output.append(('literal', data[i]))
i += 1
return output
26.8 分数背包 vs 0-1 背包
这是理解"什么时候贪心有效，什么时候无效"的最好例子。
26.8.1 分数背包（Fractional Knapsack）— 贪心有效
物品可以"切割"——可以取一部分。
def fractional_knapsack(capacity, items):
"""
分数背包：贪心法
items: [(weight, value), ...]
可以取物品的一部分
"""
# 按单位重量价值排序（从高到低）
items_with_ratio = [(v / w, w, v) for w, v in items]
items_with_ratio.sort(reverse=True)
total_value = 0
remaining = capacity
for ratio, weight, value in items_with_ratio:
if remaining <= 0:
break
if weight <= remaining:
# 全部拿走
total_value += value
remaining -= weight
else:
# 拿一部分
total_value += ratio * remaining
remaining = 0
return total_value
# 示例
items = [(10, 60), (20, 100), (30, 120)] # (weight, value)
capacity = 50
print(f"最大价值: {fractional_knapsack(capacity, items)}")
# 最大价值: 240.0
# 取全部物品1(60) + 全部物品2(100) + 2/3物品3(80) = 240
为什么贪心正确？ 因为物品可以分割，所以"单位价值最高"的策略不会浪费空间。每一份容量都被最有价值的物品填满。
26.8.2 0-1 背包 — 贪心无效
物品不可分割——要么拿，要么不拿。
# 反例：贪心策略失败
items = [(10, 60), (20, 100), (30, 120)] # (weight, value)
capacity = 50
# 贪心（按单位价值排序）：
# 物品1: ratio=6, 拿 (weight=10, value=60)
# 物品2: ratio=5, 拿 (weight=20, value=100)
# 物品3: ratio=4, 剩余30>=30, 拿 (weight=30, value=120)
# 但 10+20+30=60 > 50！物品3放不进去
# 贪心结果：只拿物品1和物品2，value=160
# 最优解：物品2+物品3，weight=50，value=220
# 贪心差了很多！
def knapsack_01_dp(capacity, items):
"""0-1 背包：只能用 DP"""
n = len(items)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
weight, value = items[i - 1]
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # 不选第 i 个
if w >= weight:
dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)
return dp[n][capacity]
print(f"0-1背包最优解: {knapsack_01_dp(50, items)}") # 220
为什么贪心失败？ 因为物品不可分割，选了"单位价值高但重量轻"的物品后，可能剩余容量只够放"单位价值低但总价值高"的物品的一小部分——而 0-1 背包不允许取一部分。贪心无法处理这种"组合效应"。
26.9 贪心适用条件速查
贪心能用的信号：
- 问题要求"最多/最少/最优"
- 每一步的选择不影响已做选择的有效性
- 能找到一个简单的排序准则
- 问题具有"交换不会更优"的性质
贪心不能用的信号：
- 当前选择会影响未来可选项的"质量"
- 需要考虑选择之间的"组合"
- 存在"选 A 导致后面只能选 B，但选 C 导致后面能选 D+E"的情况
- 问题的最优解不满足"子问题无关性"
Level 2（续） · 更多实战
26.10 分发饼干（LeetCode #455）
def find_content_children(g, s):
"""
LeetCode #455: 分发饼干
g[i]: 第 i 个孩子的胃口值
s[j]: 第 j 块饼干的大小
每个孩子最多能得到一块饼干，饼干 j 能满足孩子 i 当且仅当 s[j] >= g[i]
返回最多能满足的孩子数
贪心策略：用最小的能满足的饼干去满足胃口最小的孩子
"""
g.sort() # 孩子按胃口从小到大
s.sort() # 饼干按大小从小到大
child = 0
cookie = 0
while child < len(g) and cookie < len(s):
if s[cookie] >= g[child]:
child += 1 # 这个孩子被满足了
cookie += 1 # 无论是否满足，这块饼干都"用过"了
return child
# 示例
print(find_content_children([1, 2, 3], [1, 1])) # 1
print(find_content_children([1, 2], [1, 2, 3])) # 2
正确性直觉： 如果一块大饼干能满足一个小胃口的孩子，那用一块刚好够的小饼干去满足这个孩子，把大饼干留给大胃口的孩子，结果不会更差。这就是交换论证的直觉形式。
26.11 加油站（LeetCode #134）
def can_complete_circuit(gas, cost):
"""
LeetCode #134: 加油站
gas[i]: 第 i 个加油站能加的油
cost[i]: 从第 i 站到第 i+1 站的耗油
返回能绕一圈的起始加油站编号，不能则返回 -1
贪心策略：
1. 如果总油量 >= 总消耗，一定有解
2. 如果从 start 出发到 i 油箱变负，则 start 到 i 之间任何站都不行
（因为从 start 到中间某站 j 的油量 >= 0，从 j 出发少了这部分油更不行）
3. 所以直接从 i+1 重新开始
"""
total_tank = 0
current_tank = 0
start = 0
for i in range(len(gas)):
net = gas[i] - cost[i]
total_tank += net
current_tank += net
if current_tank < 0:
# 从 start 到 i 都不行，从 i+1 重新开始
start = i + 1
current_tank = 0
return start if total_tank >= 0 else -1
# 示例
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(can_complete_circuit(gas, cost)) # 3
为什么"跳过中间所有站"是正确的？
设从 start 出发，到达位置 j（start ≤ j ≤ i）时油箱有 tank_j ≥ 0。到位置 i 时 tank_i < 0。
如果改从 j 出发（j 在 start 和 i 之间），那到位置 i 时的油量 = tank_i - tank_j ≤ tank_i < 0（因为 tank_j ≥ 0）。
所以从 start 到 i 之间任何位置出发，到 i 时油量都是负的。只有 i+1 之后的站有可能是正确起点。
26.12 Huffman 正确性证明
定理： Huffman 算法构建的前缀码是最优的（总编码长度最短）。
证明（交换论证）：
设字母表大小为 n，字符按频率排序 f₁ ≤ f₂ ≤ ... ≤ fₙ。
引理 1： 最优树中频率最低的两个字符一定在最深层且互为兄弟。
反证：假设最优树 T 中，频率最低的 x 不在最深层。设最深层有节点 z（频率 ≥ x）。交换 x 和 z 的位置，总代价变化 = (f_x - f_z)(depth_z - depth_x)。因为 f_x ≤ f_z 且 depth_z > depth_x，所以变化 ≤ 0，即不会增加代价。与 T 最优矛盾（除非代价不变，说明 x 也可以在最深层）。
引理 2： 合并频率最低的两个字符，得到的子问题的最优解对应原问题的最优解。
设 x, y 是频率最低的两个，合并为 z（f_z = f_x + f_y）。设 T 是原问题的最优树，T' 是把 T 中 x,y 的父节点替换为叶子 z 得到的树。
cost(T) = cost(T') + f_x + f_y
因为 T' 是 n-1 个字符问题的某个解，如果它不是最优的，设 T'' 是 n-1 字符的最优解，则把 T'' 中的 z 展开为 x,y 得到的树代价 = cost(T'') + f_x + f_y < cost(T') + f_x + f_y = cost(T)，与 T 最优矛盾。
所以 T' 是 n-1 字符的最优解，归纳得证。
Level 3 · 规范怎么定义的
26.13 Huffman 1952 年论文
David A. Huffman 在 1952 年发表了《A Method for the Construction of Minimum-Redundancy Codes》（Proceedings of the IRE）。这篇论文源于他在 MIT 读研时 Robert Fano 的课上的一次作业——Fano 给学生两个选择：做期末考试，或者找到最优的二进制编码方法。Huffman 选择了后者，在数月苦思后发现了这个贪心算法。
讽刺的是，Fano 本人之前提出的 Shannon-Fano 编码（自顶向下分割）并不是最优的，而他的学生从底向上合并的方法却是最优的。这个故事完美诠释了"自底向上贪心"有时比"自顶向下分治"更好。
Huffman 论文的核心贡献：
- 证明了前缀码的最优性可以通过贪心构造达到
- 给出了 O(n log n) 的构造算法
- 证明了 Huffman 编码的平均码长满足 H(X) ≤ L < H(X) + 1，其中 H(X) 是信源熵
这个 H(X) ≤ L < H(X) + 1 的界来自 Shannon 1948 年的信息论奠基论文。它告诉我们：Huffman 编码最多比理论极限（熵）多 1 bit/symbol。现代的算术编码（Arithmetic Coding）可以逼近熵，但 Huffman 编码因为简单高效，至今仍广泛使用。
26.14 贪心与拟阵（Matroid）理论
26.14.1 什么是拟阵
拟阵（matroid）是一种组合结构，由 Hassler Whitney 在 1935 年提出，用于抽象"独立性"的概念。一个拟阵 M = (S, I) 由有限集 S 和独立集族 I ⊆ 2^S 构成，满足：
- 空集独立：∅ ∈ I
- 遗传性（hereditary）：如果 A ∈ I 且 B ⊆ A，则 B ∈ I
- 交换性（exchange property）：如果 A, B ∈ I 且 |A| < |B|，则存在 x ∈ B\A 使得 A ∪ {x} ∈ I
26.14.2 贪心在拟阵上总是最优
定理（Rado 1957，Edmonds 1971）： 如果问题的可行解构成一个拟阵，且目标是最大化权重，那么按权重从大到小贪心地加入元素（只要保持独立）就得到最优解。
这个定理解释了为什么以下贪心算法是正确的：
Kruskal 最小生成树（第 18 章）：
- 集合 S = 所有边
- 独立集 I = 不构成环的边的子集（即森林）
- 这构成一个"图拟阵"（graphic matroid）
- 贪心：按权重从小到大选边，跳过会成环的
- 正确性由拟阵定理保证
活动选择（本章）：
- 严格来说，活动选择不直接是一个拟阵问题（因为"不重叠"不满足遗传性的一般形式）
- 但它可以通过"区间图着色"转化为拟阵问题
- 更简单的证明是直接用交换论证
26.14.3 拟阵视角下的贪心通用框架
def greedy_on_matroid(elements, weight_fn, is_independent):
"""
拟阵上的贪心算法（通用框架）
elements: 基础集合 S
weight_fn: 权重函数 w: S → R
is_independent: 判断子集是否独立的函数
返回最大权重独立集
"""
# 按权重从大到小排序
sorted_elements = sorted(elements, key=weight_fn, reverse=True)
result = set()
for e in sorted_elements:
# 如果加入 e 后仍然独立，就加入
if is_independent(result | {e}):
result.add(e)
return result
# 示例：Kruskal 算法
def kruskal_via_matroid(n, edges):
"""用拟阵框架实现 Kruskal"""
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
uf = UnionFind(n)
# 按权重从小到大（最小生成树）
edges.sort(key=lambda e: e[2])
mst = []
for u, v, w in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append((u, v, w))
return mst
26.15 Kruskal 贪心正确性的拟阵证明
在第 18 章中我们用"剪切性质"证明了 Kruskal 算法的正确性。这里我们用拟阵理论给出另一个视角。
图拟阵定义：
- S = 图的所有边
- I = {A ⊆ S : A 中的边不构成环}（即 A 是一个森林）
验证三条公理：
- 空集是森林 ✓
- 森林的子集仍是森林 ✓
- 交换性：设 A, B 是两个森林且 |A| < |B|。A 有 n-1-|A| 个连通分量，B 有 n-1-|B| 个。因为 |A| < |B|，A 的连通分量更多。必存在一条边 e ∈ B\A 连接了 A 中的两个不同分量，则 A ∪ {e} 仍无环 ✓
Rado 定理应用： 对于最小生成树，我们想最小化总权重。等价于最大化"负权重"。按 Rado 定理，贪心（按权重从小到大选，跳过成环的）得到的就是最大权重独立集 = 最小生成树。
26.16 贪心 vs DP 的理论边界
从计算复杂度角度：
- 贪心通常 O(n log n)——排序后线性扫描
- DP 通常 O(n²) 或 O(n × W)——需要填表
- 如果一个问题既能用贪心也能用 DP，贪心总是更快
从问题结构角度（CLRS 教材的分类）：
- 贪心选择性质：全局最优解包含局部最优选择
- 最优子结构：最优解的子问题解也是子问题的最优解
- DP 只需要最优子结构
- 贪心同时需要贪心选择性质和最优子结构
这解释了一个重要现象：能用贪心解的问题一定能用 DP 解（DP 更通用），但能用 DP 解的问题不一定能用贪心解（贪心更特殊）。
Level 4 · 边界与陷阱
26.17 面试题精选
26.17.1 LeetCode #455: 分发饼干
（已在 26.10 详细讲解）
关键点：排序 + 双指针。时间 O(n log n + m log m)，空间 O(1)。
26.17.2 LeetCode #435: 无重叠区间
（已在 26.3.2 详细讲解）
关键点：转化为"最大不重叠区间数"，答案 = 总数 - 最大不重叠。
26.17.3 LeetCode #452: 用最少数量的箭引爆气球
（已在 26.3.3 详细讲解）
关键点：等价于"最大不重叠区间数"（注意边界：相切也算重叠）。
26.17.4 LeetCode #134: 加油站
（已在 26.11 详细讲解）
关键点：总量判断可行性 + 局部重置找起点。
26.17.5 更多面试贪心题
def lemonade_change(bills):
"""
LeetCode #860: 柠檬水找零
顾客按顺序付 5/10/20 美元，柠檬水 5 美元
能否给每个顾客正确找零？
贪心：优先用大面额找零
"""
five = ten = 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
if five == 0:
return False
five -= 1
ten += 1
else: # 20
# 优先用 10+5 找零（贪心：保留更多5块）
if ten > 0 and five > 0:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True
def partition_labels(s):
"""
LeetCode #763: 划分字母区间
把字符串划分为尽可能多的片段，使每个字母只出现在一个片段中
贪心：每个片段的右边界取所有已包含字符的最远出现位置
"""
# 记录每个字符最后出现的位置
last = {c: i for i, c in enumerate(s)}
partitions = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c]) # 扩展右边界
if i == end: # 到达当前片段的右边界
partitions.append(end - start + 1)
start = end + 1
return partitions
def reorganize_string(s):
"""
LeetCode #767: 重构字符串
重新排列字符使得相邻字符不同，如不可能返回空串
贪心 + 优先队列：每次放频率最高的（且和上一个不同的）字符
"""
from collections import Counter
import heapq
freq = Counter(s)
# 最大堆（用负数模拟）
heap = [(-count, char) for char, count in freq.items()]
heapq.heapify(heap)
result = []
prev_count, prev_char = 0, ''
while heap:
count, char = heapq.heappop(heap)
result.append(char)
# 把上一个字符放回堆（如果还有剩余）
if prev_count < 0:
heapq.heappush(heap, (prev_count, prev_char))
prev_count = count + 1 # 用了一个，计数+1（负数所以是+1）
prev_char = char
return ''.join(result) if len(result) == len(s) else ''
26.18 什么时候贪心，什么时候 DP
这是面试中最常被追问的元问题。以下是决策框架：
Step 1: 问题是否有"贪心选择性质"？
测试方法：假设你做了一个贪心选择（如"选最小的"、"选最早结束的"），能否证明存在一个包含这个选择的最优解？
- 如果能证明 → 可能可以贪心
- 如果能构造反例 → 必须用 DP 或其他方法
Step 2: 构造反例
# 尝试构造反例的通用方法：
# 1. 设计只有 2-3 个元素的小 case
# 2. 看贪心选择是否导致错误
# 例：硬币找零
# 面额 [1, 5, 10, 25]，金额 30
# 贪心：25+5 = 2 枚 ✓
# 面额 [1, 3, 4]，金额 6
# 贪心：4+1+1 = 3 枚 ✗（最优：3+3 = 2 枚）
# 结论：一般硬币找零不能贪心（但特定面额系统可以）
Step 3: 经典问题分类
| 问题 | 贪心 or DP | 原因 |
|---|---|---|
| 活动选择/区间调度 | 贪心 | 选最早结束的不影响后续选择质量 |
| 分数背包 | 贪心 | 可分割→单位价值排序 |
| 0-1 背包 | DP | 不可分割→选 A 影响剩余容量→影响后续选择 |
| 最长公共子序列 | DP | 选一个字符影响后续匹配 |
| 最短路径（无负权） | 贪心(Dijkstra) | 已确定的最短路不会被更长路径改善 |
| 最短路径（有负权） | DP(Bellman-Ford) | 负权边可能使已确定的路径变得不最优 |
| 哈夫曼编码 | 贪心 | 合并最低频满足拟阵条件 |
| 硬币找零（一般） | DP | 面额组合有"干扰"效应 |
| 跳跃游戏 | 贪心 | 每一步能到的范围只取决于已走过的位置 |
| 编辑距离 | DP | 每一步操作相互依赖 |
面试回答模板： "这个问题我先考虑能不能贪心。贪心的前提是'局部最优能导向全局最优'。让我试试 [具体贪心策略]... [如果能证明/构造反例] 所以这个问题应该用 [贪心/DP]。"
26.19 贪心的边界 Case
贪心看似对但实际错的陷阱
# 陷阱 1：旅行商问题（TSP）
# "每次去最近的未访问城市" — 贪心！
# 但这是 NP-hard 问题，贪心不能保证最优。
# 反例：4个城市在正方形顶点，贪心走边，最优走对角线。
# 陷阱 2：最长递增子序列（LIS）
# "贪心选当前能选的最小的" — 不对！
# LIS 需要 DP（O(n²)）或 贪心+二分（O(n log n)，但这个"贪心"本质是 DP）
# 陷阱 3：任务分配
# "给最快的人分最重的任务" — 不一定对！
# 取决于具体的目标函数（最小化最大完成时间 vs 最小化总完成时间）
贪心正确但难以证明的情况
def max_profit_job_scheduling(startTime, endTime, profit):
"""
LeetCode #1235: 规划兼职工作
看起来像贪心（按结束时间排序选最赚的），但实际需要 DP。
这个问题是"带权区间调度"（Weighted Interval Scheduling），
权重不同使得简单贪心失效。
"""
import bisect
jobs = sorted(zip(endTime, startTime, profit))
n = len(jobs)
dp = [0] * (n + 1)
for i in range(1, n + 1):
end, start, p = jobs[i - 1]
# 二分查找最后一个结束时间 <= 当前开始时间的 job
k = bisect.bisect_right([j[0] for j in jobs[:i]], start)
dp[i] = max(dp[i - 1], dp[k] + p)
return dp[n]
26.20 与本站其他章节的联系
- 第 18 章（图的最短路径与最小生成树） — Kruskal 和 Prim 算法都是贪心的经典应用。Kruskal 的正确性可以用本章的拟阵理论优雅地证明。
- 第 25 章（动态规划） — DP 是贪心的"加强版"。当贪心不正确时，DP 是保底选择。理解两者的边界是算法面试的核心能力。
- 本站 MySQL 书 — Huffman 编码在 InnoDB 压缩页（COMPRESS）中有应用。InnoDB 的页压缩使用 zlib，而 zlib 内部就是 LZ77 + Huffman。
本章小结
贪心算法是最"赌"的算法范式——它在每一步做出不可逆的局部最优选择，赌这些选择能组合成全局最优。这个赌注有时对（活动选择、Huffman 编码、Kruskal），有时错（0-1 背包、TSP、一般硬币找零）。
区分贪心是否正确的能力，是算法素养的核心。本章的关键外带：
- 贪心三要素：贪心选择性质 + 最优子结构 + 无后效性
- 证明方法：交换论证（最常用）和反证法
- 核心模式：区间调度按右端点、Huffman 合最小、背包按单位价值
- 决策框架：先尝试贪心→构造反例→不行就用 DP
- 数学基础：拟阵理论给出了"贪心何时正确"的完整理论框架
Huffman 在 1952 年用一个研究生作业改变了信息论；Bayer 在 1972 年用 B-Tree 改变了数据库；O'Neil 在 1996 年用 LSM-Tree 改变了存储系统。这些影响深远的贡献，核心思想往往简洁到令人惊叹——这正是贪心的美学：用最简单的规则，解决最复杂的问题。