贪心算法：局部最优与全局最优的证明艺术
贪心算法每次都做出局部最优选择，期望最终得到全局最优解。并非所有问题都适用贪心，但一旦适用，贪心往往是最简洁高效的解法。
一、贪心 vs 动态规划
| 特性 | 贪心 | 动态规划 |
|---|---|---|
| 选择 | 只做一个，不回溯 | 考虑所有子问题 |
| 性质要求 | 贪心选择性质 | 最优子结构 |
| 复杂度 | 通常更低 | 通常更高 |
| 正确性 | 需证明 | 自底向上保证 |
关键区别：贪心选择性质要求「局部最优选择 + 子问题的最优解 = 全局最优解」。
二、经典问题
1. 活动选择问题（Activity Selection）
给定 n 个活动的开始和结束时间，选择最多不重叠的活动。
贪心策略：每次选择结束时间最早且不与已选活动冲突的活动。
def activity_selection(activities):
"""activities: [(start, end), ...]"""
activities.sort(key=lambda x: x[1]) # 按结束时间排序
selected = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
正确性证明（交换论证）：
设贪心解为 G，最优解为 O。假设 O 的第一个活动结束时间晚于 G 的第一个活动，用 G 的第一个活动替换 O 的第一个，不减少活动数量，逐步将所有差异替换，证明 G 也是最优的。
2. Jump Game（LeetCode 55）
def can_jump(nums):
max_reach = 0
for i, num in enumerate(nums):
if i > max_reach:
return False
max_reach = max(max_reach, i + num)
return True
3. 分发糖果（LeetCode 135）
两次贪心：从左到右满足评分高的糖果多，从右到左再调整。
def candy(ratings):
n = len(ratings)
candies = [1] * n
# 从左到右
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# 从右到左
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)
4. 重构字符串（LeetCode 767）— 贪心 + 优先队列
import heapq
from collections import Counter
def reorganize_string(s):
count = Counter(s)
max_heap = [(-freq, char) for char, freq in count.items()]
heapq.heapify(max_heap)
result = []
prev_freq, prev_char = 0, ''
while max_heap:
freq, char = heapq.heappop(max_heap)
result.append(char)
# 上次取出的字符重新入堆
if prev_freq < 0:
heapq.heappush(max_heap, (prev_freq, prev_char))
prev_freq, prev_char = freq + 1, char
return ''.join(result) if len(result) == len(s) else ''
三、最小生成树
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
def kruskal(n, edges):
"""edges: [(u, v, weight), ...]"""
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
mst = []
for u, v, w in edges:
if uf.union(u, v):
mst.append((u, v, w))
if len(mst) == n - 1:
break
return mst
Prim 算法
从某个顶点开始，每次选连接树与非树的最小边。
import heapq
def prim(n, graph):
"""graph: {u: [(v, weight), ...]}"""
visited = [False] * n
min_heap = [(0, 0)] # (weight, node)
mst_weight = 0
edges = []
while min_heap:
w, u = heapq.heappop(min_heap)
if visited[u]:
continue
visited[u] = True
mst_weight += w
for v, weight in graph[u]:
if not visited[v]:
heapq.heappush(min_heap, (weight, v))
edges.append((u, v, weight))
return mst_weight, edges
| 算法 | 时间复杂度 | 适用场景 |
|---|---|---|
| Kruskal | O(E log E) | 稀疏图，边已排序 |
| Prim | O((V + E) log V) | 稠密图 |
四、Huffman 编码
贪心构建最优前缀编码树。
import heapq
from collections import defaultdict, Counter
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = self.right = None
def __lt__(self, other):
return self.freq < other.freq
def huffman(text):
freq = Counter(text)
heap = [Node(c, f) for c, f in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = Node(None, left.freq + right.freq)
merged.left, merged.right = left, right
heapq.heappush(heap, merged)
# 生成编码
codes = {}
def generate_codes(node, code):
if node.char:
codes[node.char] = code or '0'
return
generate_codes(node.left, code + '0')
generate_codes(node.right, code + '1')
generate_codes(heap[0], '')
return codes
五、贪心正确性证明方法
1. 交换论证（Exchange Argument）
证明贪心解可以逐步转换为最优解，且转换过程不降低解的质量。
2. 归纳法（Induction）
证明贪心选择的每一步都保持最优子结构。
3. 反证法（Contradiction）
假设存在比贪心解更好的解，导出矛盾。
六、面试常见问题
Q: 如何判断一个问题能否用贪心？
- 问题具有最优子结构
- 局部最优选择能导致全局最优（贪心选择性质）
- 如果无法证明贪心正确性，考虑 DP
Q: 区间问题的贪心策略有哪些？
- 最早结束时间 → 最多不重叠区间
- 最早开始时间 → 最少会议室（配合优先队列）
- 最短区间 → 不一定最优
Q: Dijkstra 是贪心吗？
是。每次选距离源点最近的未访问节点，用贪心得到单源最短路径（边权非负时正确）。
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。