引言 (Introduction)
贪心算法（Greedy Algorithm）是算法设计中极具魅力的一类方法：它不做长远规划，只做当前看起来最优的选择。这种"短视"策略在某些问题上恰好能得到全局最优解，而在另一些问题上则会落入局部陷阱。
这种两极化的表现构成了学习贪心算法的核心挑战：不是会不会写贪心，而是能不能判断该不该用贪心。动态规划（DP）和贪心经常面对同一类问题，前者稳妥但开销大，后者高效但适用范围窄。理解两者之间的"安全边界"是本文的核心目标。
本文是本系列第一篇，聚焦于贪心算法的理论基础与最基础的贪心问题。我们将从形式化定义出发，建立贪心与 DP 的对比框架，再通过三道 LeetCode 入门题将理论落地为代码。
1. 贪心算法的理论基础
1.1 贪心选择性质
定义（贪心选择性质）：一个问题具有贪心选择性质，当且仅当通过做出局部最优选择，可以逐步构建出一个全局最优解。换言之，第一个贪心选择不排除全局最优解的可能性。
贪心选择的关键特征是无后效性：做决策时只看当前状态，不需要为未来的选择预留信息。
全局最优
↑
│ 贪心选择 n
│ ↑
│ 贪心选择 2
│ ↑
│ 贪心选择 1
│ ↑
初始状态
1.2 最优子结构
定义（最优子结构）：一个问题的最优解包含其子问题的最优解。这是贪心和 DP 的共同前提——没有最优子结构，两者都无从谈起。
以分数背包（Fractional Knapsack）为例：选择一件物品后，剩余容量上的最优解与原问题的最优解是兼容的。这个结构保证了贪心策略的合法性。
1.3 贪心 vs 动态规划：形式化对比
| 维度 | 贪心 | 动态规划 |
|---|---|---|
| 决策方式 | 每一步做局部最优选择，不回头 | 枚举所有可能选择，取最优 |
| 状态空间 | 只保留一个状态（当前最优） | 保留所有可能的状态 |
| 时间复杂度 | 通常 $O(n \log n)$ 或 $O(n)$ | 通常 $O(n^2)$ 或更高 |
| 空间复杂度 | $O(1)$ | 通常 $O(n)$ |
| 适用范围 | 需要贪心选择性质 | 需要最优子结构（更普适） |
| 正确性保证 | 需要额外证明 | 由状态转移方程保证 |
关键洞察：凡是贪心能解的问题，DP 也一定能解；反过来则不成立。那么为什么还要学贪心？——因为贪心在它适用的场景下，时间复杂度和空间复杂度远优于 DP。将 $O(n^2)$ 降到 $O(n)$，这在实际工程中可能是「能跑」与「跑不动」的区别。
用一个经典问题来感受这种差异：
零钱兑换问题：给定硬币面值 coins = [1, 5, 10, 25] 和总金额 amount = 63，最少用几枚硬币？
- 贪心：每次都选最大面值。$25 + 25 + 10 + 1 + 1 + 1 = 63$，共 6 枚。
- DP：填写一个长度为 64 的数组，对每个金额枚举所有硬币。
在这个面值体系下贪心恰好正确（美国硬币面值满足贪心性质），时间复杂度为 $O(k)$（$k$ 为硬币种类数），而 DP 需要 $O(n \cdot k)$。但如果硬币换为 [1, 3, 4]，贪心就失效了——$6$ 的最优解是 $3+3$（2 枚），而贪心会给出 $4+1+1$（3 枚）。
这个例子揭示了学习贪心的核心法则：永远不要默认贪心是正确的，要么证明它，要么放弃它。
2. 贪心正确性的两种证明方法
2.1 归纳法（Induction）
证明思路：假设前 $k$ 步的贪心选择是某个最优解的一部分，证明第 $k+1$ 步的贪心选择仍然可以被扩展到某个最优解中。
模板：
- 基础情形（$k=0$）：空选择集可以被扩展到某个最优解（显然成立）。
- 归纳步：假设前 $k$ 步贪心选择 $\{g_1, \ldots, g_k\}$ 存在于某最优解 $OPT$ 中，证明 $g_{k+1}$ 也可被 $OPT$ 容纳。
- 结论：$n$ 步后，贪心解 = 最优解。
2.2 交换论证法（Exchange Argument）
证明思路：假设存在一个比贪心解更优的解 $OPT$，通过逐步交换将 $OPT$ 转换为贪心解，每次交换不降低解的质量，从而证明贪心解不差于 $OPT$。
模板：
- 令贪心解为 $G$，假设存在更优解 $OPT$。
- 找到 $G$ 与 $OPT$ 第一个分歧的选择。
- 构造一个新的解 $OPT'$：将 $OPT$ 在该位置的选择替换为贪心选择，证明 $OPT'$ 不劣于 $OPT$。
- 重复此过程，最终将 $OPT$ 转换为 $G$ 而质量不降，矛盾。
这两种方法在后文的题目分析中将反复出现。我们先从不需要证明的"显然贪心"题目入手。
3. LeetCode 455：分发饼干
题目：每个孩子有一个胃口值 $g[i]$，每块饼干有一个尺寸 $s[j]$。当 $s[j] \ge g[i]$ 时，饼干 $j$ 可以满足孩子 $i$。每个孩子最多给一块饼干。问最多能满足多少孩子。
3.1 贪心策略
直觉：用最小的能满足该孩子的饼干去喂它——把更大的饼干留给胃口更大的孩子。
具体做法：对 $g$ 和 $s$ 排序，双指针从左到右扫描。若当前饼干能满足当前孩子，两者都前进；否则饼干太小，换下一块饼干。
这个策略的贪心优先级是明确的：优先满足最容易满足的孩子。
3.2 完整代码
from typing import List
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
i = j = 0
while i < len(g) and j < len(s):
if s[j] >= g[i]:
i += 1 # 喂饱了孩子 i
j += 1 # 饼干 j 已被消耗（或太小而跳过）
return i
复杂度：排序 $O(n \log n + m \log m)$，双指针 $O(n+m)$，总体 $O(n \log n + m \log m)$。空间 $O(1)$（忽略排序的栈开销）。
3.3 交换论证证明
设贪心解匹配了 $k$ 个孩子 $(g_{i_1}, s_{j_1}), \ldots, (g_{i_k}, s_{j_k})$。假设存在一个更优解匹配了 $k+1$ 个孩子。
在贪心解中，对于第一个孩子 $g_{i_1}$，贪心选择了能喂饱它的最小饼干 $s_{j_1}$。假想最优解给孩子 $g_{i_1}$ 分配了另一块饼干 $s'$（显然 $s' \ge g_{i_1}$）。若 $s' \ge s_{j_1}$，我们可以将最优解中的 $s'$ 换为更小的 $s_{j_1}$，释放出 $s'$ 给后面的孩子使用——匹配数不会减少。逐位交换后，最优解等价于贪心解，矛盾。故贪心解即为最优。
4. LeetCode 860：柠檬水找零
题目：柠檬水 5 元一杯。顾客排队购买，每人付一张钞票（5、10 或 20 元）。初始手中无零钱。问能否给每位顾客正确找零。
4.1 贪心策略
收到 20 元时面临选择：找零 $10 + 5$（优先），还是 $5 + 5 + 5$。
贪心策略：优先用大面额（10 元）找零，保留小面额（5 元）的灵活性。因为 10 元只能用于找 20 元，而 5 元可用于找 10 元和 20 元——5 元是更"宝贵"的资源。
4.2 完整代码
from typing import List
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
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: # bill == 20
# 贪心：优先消耗一张 10 元 + 一张 5 元
if ten > 0 and five > 0:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True
复杂度：时间 $O(n)$，空间 $O(1)$。
4.3 正确性证明
用 10 元找零 20 元时，消耗的是「只能用于找 20 元」的资源；用 5 元找零 20 元时，消耗的是「可以用于找 10 元和 20 元」的通用资源。显然后者更贵。贪心策略始终选择廉价资源先消耗，保存昂贵资源的灵活性，从而在任意顾客序列下都是最优的。
5. LeetCode 122：买卖股票的最佳时机 II
题目：给定一个数组 prices，其中 prices[i] 是第 $i$ 天的股票价格。你可以进行任意多次交易（买入+卖出算一次），但最多持有一股。求最大利润。
5.1 贪心策略
直觉：抓住每一段上涨。只要明天的价格比今天高，今天就买入、明天就卖出。
更精确地说：总利润等于所有正向价格差的累加——$\sum_{i=1}^{n-1} \max(0, prices[i] - prices[i-1])$。
prices = [7, 1, 5, 3, 6, 4]
7 1 5 3 6 4
\ / \ / \ / \ /
-6 +4 -2 +3 -2
贪心利润 = 4 + 3 = 7（第 2 天买，第 3 天卖；第 4 天买，第 5 天卖）
这个策略之所以正确，是因为它等价于「在任何上坡都持有股票」——而上坡的累计收益恰好等于相邻正差之和。
5.2 完整代码
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
diff = prices[i] - prices[i - 1]
if diff > 0:
profit += diff
return profit
复杂度：时间 $O(n)$，空间 $O(1)$。
5.3 形式化证明
令 $P_L = \sum_{i \in \text{long}} (prices[i] - prices[i-1])$ 为任意"持有期"策略的收益。由于持有期由若干不相交的区间 $[a_1, b_1], [a_2, b_2], \ldots$ 构成，每段的收益为 $prices[b_k] - prices[a_k]$，这恰好等于该区间内所有相邻差之和：
$$prices[b_k] - prices[a_k] = \sum_{i=a_k+1}^{b_k} (prices[i] - prices[i-1])$$因此任何策略的收益均可表示为某些相邻差的加和。显然，选取所有正差的和是上界，而贪心策略恰好达到了这个上界。证毕。
6. 本章小结
本文完成了贪心算法的三项基础建设：
- 概念框架：贪心选择性质 + 最优子结构，以及与 DP 的边界对比。
- 证明工具：归纳法和交换论证法——这是判断贪心是否正确的"安检闸门"。
- 入门实战：三道基础题（455 分发饼干、860 找零、122 买卖股票）——这三题的核心贪心直觉分别是「最小代价优先」「保护灵活资源」「累加所有正向变化」。
从复杂度来看，这三题的贪心解都是 $O(n)$ 或 $O(n \log n)$，空间均为 $O(1)$，体现了贪心"快且省"的优势。
结论 (Conclusion)
本文建立了贪心算法的理论基石并走过了最简单的贪心问题。但这三道题的贪心策略都相对明显——“直觉上就该这么做”。下一篇我们将进入贪心算法最具代表性的领域——区间调度问题，那里将有更多的反直觉陷阱和更复杂的正确性证明。我们将面对这样的问题：为什么「按结束时间排序」能取得最优？为什么「按开始时间排序」反而会错？
下一篇预览：区间调度与活动选择（LeetCode 435、452、56），以及「最少箭射气球」和「合并区间」的贪心建模技巧。