贪心算法：局部最优与全局最优

简介

贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。其核心思想是“活在当下”，只关注眼前的局部最优解，而不考虑长远的整体影响。这种策略在直觉上非常吸引人，因为它简化了决策过程，但并非在所有问题上都有效。贪心算法的有效性高度依赖于问题的特定结构，只有当局部最优解的组合能保证全局最优解时，该算法才是正确的。

与需要穷举所有可能性的暴力搜索或记录并复用子问题解的动态规划相比，贪心算法通常更为高效，时间复杂度更低，空间消耗也更少。然而，其应用范围相对较窄。本章将深入探讨贪心算法有效的两个关键条件：贪心选择性质和最优子结构，并通过一系列经典问题来展示如何识别和应用贪心策略。理解这些条件是将贪心算法从一种直觉性试探转变为可靠工具的关键。

核心概念

贪心算法的正确性建立在两个核心性质之上：贪心选择性质和最优子结构。这两个性质共同保证了局部最优的连续选择能够导向全局最优解。

贪心选择性质：一个问题的全局最优解可以通过一系列局部最优（贪心）选择来达到。这意味着，在每一步，我们都可以做出一个在当前看来最好的选择，并且这个选择不会被后续的决策所推翻。我们不需要为了全局最优而考虑所有可能的子问题解，只需做出贪心选择即可。

最优子结构：一个问题的最优解包含其子问题的最优解。这与动态规划中的最优子结构概念相同。如果一个问题在做出贪心选择后，剩下的子问题与原问题具有相同的结构，并且该子问题的最优解能与之前的贪心选择合并成原问题的最优解，那么该问题就具有最优子结构。

贪心与动态规划的对比 这是一个至关重要的区分点。两者都要求问题具有最优子结构，但关键区别在于贪心选择性质。 - 动态规划：在每一步，动态规划会考虑所有可能的选择（通常通过递归关系式），并记录下每个子问题的最优解（记忆化），最终通过组合这些子解来构建全局最优解。它“瞻前顾后”，确保没有遗漏更好的组合。 - 贪心算法：在每一步，它只做出一个看起来最好的选择，并且一旦做出就不再回头（不可撤销）。它“一往无前”，相信当前的最佳选择会引导至最终的最佳结果。

简而言之，动态规划是自底向上或带记忆的自顶向下求解，而贪心算法是自顶向下地做出一系列不可撤销的选择。能用贪心解决的问题，动态规划一定能解，但反之则不成立。贪心算法通常是动态规划的一个特例，其中动态规划的状态转移方程中的“max/min”操作，总是由某个贪心准则直接决定。

实战示例

下面我们通过几个经典问题来具体阐释贪心算法的应用。首先从“分发饼干”这个简单问题开始。

示例一：分发饼干 (Assign Cookies)

问题描述：你是一位很棒的家长，想要给你的孩子们一些饼干。每个孩子 i 有一个胃口值 g[i]，这是能让孩子满足的最小饼干尺寸；每块饼干 j 有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将饼干 j 分配给孩子 i，这个孩子会得到满足。你的目标是尽可能满足更多数量的孩子，并输出这个最大数值。

贪心策略：为了满足更多的孩子，对于每一个孩子，我们应该给他能满足他胃口的最小尺寸的饼干。这样，更大的饼干可以留给胃口更大的孩子。实现上，可以先将孩子和饼干的数组分别排序，然后用两个指针依次匹配。

def find_content_children(g, s):
"""
分发饼干 - 贪心算法实现
:param g: List[int] 孩子的胃口值列表
:param s: List[int] 饼干的尺寸列表
:return: int 最多可以满足的孩子数量
"""
# 排序是贪心策略的关键前提
g.sort()
s.sort()
child_index = 0  # 指向当前待满足的孩子
cookie_index = 0  # 指向当前待分配的饼干
content_children = 0
# 遍历孩子和饼干
while child_index < len(g) and cookie_index < len(s):
# 如果当前饼干能满足当前孩子的胃口
if s[cookie_index] >= g[child_index]:
content_children += 1  # 满足一个孩子
child_index += 1       # 考虑下一个孩子
# 无论当前饼干是否被使用，都考虑下一块饼干（如果没被使用，说明它太小，无法满足当前及以后的孩子）
cookie_index += 1
return content_children
# 测试代码
if __name__ == "__main__":
children = [1, 2, 3]  # 三个孩子的胃口
cookies = [1, 1]      # 两块饼干
result = find_content_children(children, cookies)
print(f"最多可以满足 {result} 个孩子")  # 输出：最多可以满足 1 个孩子
children2 = [1, 2]
cookies2 = [1, 2, 3]
result2 = find_content_children(children2, cookies2)
print(f"最多可以满足 {result2} 个孩子")  # 输出：最多可以满足 2 个孩子

示例二：无重叠区间 (Non-overlapping Intervals)

问题描述：给定一个区间集合 intervals，找到需要移除区间的最小数量，使剩余区间互不重叠。区间 [1,2] 和 [2,3] 的边界接触不算重叠。

贪心策略：此问题等价于“最多能保留多少个互不重叠的区间”。一个经典的贪心策略是按照区间的结束时间进行升序排序。然后，我们总是选择结束时间最早的且不与已选区间重叠的区间。为什么按结束时间排序？因为一个区间结束得越早，留给后面区间的时间就越多，可能容纳的区间就越多。

def erase_overlap_intervals(intervals):
"""
无重叠区间 - 贪心算法实现
:param intervals: List[List[int]] 区间列表，每个区间为 [start, end]
:return: int 需要移除的最小区间数量
"""
if not intervals:
return 0
# 关键步骤：按照区间的结束时间进行排序
intervals.sort(key=lambda x: x[1])
# 初始化：第一个区间（结束最早的）一定被保留
count = 1  # 记录保留的区间数量
end = intervals[0][1]  # 当前已保留区间的结束时间
# 遍历后续区间
for i in range(1, len(intervals)):
# 如果当前区间的开始时间 >= 上一个保留区间的结束时间，则不重叠，可以保留
if intervals[i][0] >= end:
count += 1
end = intervals[i][1]  # 更新结束时间
# 需要移除的数量 = 总区间数 - 保留的区间数
return len(intervals) - count
# 测试代码
if __name__ == "__main__":
test_intervals = [[1,2], [2,3], [3,4], [1,3]]
result = erase_overlap_intervals(test_intervals)
print(f"需要移除 {result} 个区间使剩余区间无重叠")  # 输出：需要移除 1 个区间 ([1,3])

示例三：用最少数量的箭引爆气球 (Minimum Number of Arrows to Burst Balloons)

问题描述：在二维平面上有一些气球，输入是每个气球的水平直径的开始和结束坐标 points[i] = [x_start, x_end]。射出一支箭，若箭的 x 坐标在 x_start 和 x_end 之间（含边界），则该气球会被引爆。求引爆所有气球所必须射出的最小弓箭数。

贪心策略：这个问题可以转化为“无重叠区间”问题的变体。如果多个气球的区间有重叠，那么一支箭就可以射爆它们。因此，问题变为：找到一组点（箭的位置），使得每个区间至少包含一个点，求点的最小数量。这与寻找最大数量的互不相交区间（每支箭解决一组重叠区间中的一个代表）的思路恰好互补。我们依然按结束坐标排序，但判断重叠的条件变为 当前开始 <= 上次结束（因为边界接触也算重叠，可以一箭射爆）。一旦不重叠，就需要一支新箭。

def find_min_arrow_shots(points):
"""
引爆气球 - 贪心算法实现
:param points: List[List[int]] 气球区间列表
:return: int 所需的最少箭数
"""
if not points:
return 0
# 按气球的结束坐标升序排序
points.sort(key=lambda x: x[1])
arrows = 1  # 至少需要一支箭
current_end = points[0][1]  # 第一支箭可以射爆的结束位置（理论上可以放在current_end这个点）
for start, end in points[1:]:
# 如果当前气球的开始位置 > 上一支箭能覆盖的结束位置，说明需要一支新箭
if start > current_end:
arrows += 1
current_end = end  # 新箭可以覆盖到当前气球的结束位置
return arrows
# 测试代码
if __name__ == "__main__":
balloons = [[10,16], [2,8], [1,6], [7,12]]
result = find_min_arrow_shots(balloons)
print(f"引爆所有气球需要至少 {result} 支箭")  # 输出：引爆所有气球需要至少 2 支箭
# 解释：一支箭在 x=6 射爆 [2,8],[1,6]，另一支在 x=11 射爆 [10,16],[7,12]

对比分析

下表总结了本章涉及的几个经典贪心问题及其策略核心，并与动态规划的可能解法进行对比。

最佳实践

1. 先验证性质，再应用算法：在尝试使用贪心算法前，务必从贪心选择性质和最优子结构两个角度进行思考或简单证明。可以通过举反例来测试策略是否总是有效。一个常见的证明技巧是“替换法”：假设存在一个最优解，证明可以将其第一步替换为贪心选择，而解的质量不会变差。
2. 排序是贪心的好朋友：许多贪心问题（尤其是区间类、分配类问题）的第一步都是对输入数据进行排序（按开始时间、结束时间、大小、权重等）。正确的排序方式能将问题的结构展现出来，使得贪心选择变得显而易见。
3. 维护关键变量，一次遍历解决：贪心算法通常效率极高，在排序之后（O(n log n)）或直接在一次遍历（O(n)）中即可解决问题。在遍历过程中，需要精心设计并维护一个或几个关键变量（如当前结束时间、当前可达最远距离、总油量剩余等），这些变量代表了做出贪心选择后的系统状态。
4. 从简单问题开始培养直觉：熟练掌握“分发饼干”、“跳跃游戏I”这类简单问题，有助于建立对贪心算法适用场景的直觉。对于更复杂的问题，可以尝试先提出一个贪心策略，然后检验其是否正确，或者思考如何将其转化为已知的贪心模型（如区间调度模型）。

小结

贪心算法以其高效和简洁著称，其核心在于通过每一步的局部最优选择来构造全局最优解。成功应用贪心算法的关键在于识别问题是否具备贪心选择性质和最优子结构。本章通过分发饼干、无重叠区间、引爆气球等经典例题，展示了如何通过排序和一次遍历来实现贪心策略，并与动态规划方法进行了对比，突出了贪心算法在效率上的优势。掌握这些经典模型，能够帮助我们在遇到新问题时，快速判断贪心算法是否适用，并设计出正确的贪心准则。

下一节：图论算法基础：表示、遍历与拓扑排序