贪心算法

贪心算法是最"直观"的算法——每一步都选最优。但面试官想知道的是：你怎么知道这道题能用贪心？

面试考察点

面试官通过这道题想考察：
1. 你是否能判断一个问题是否适合贪心
2. 你是否能证明贪心的正确性
3. 你是否能理解贪心与 DP 的区别
4. 你是否能举出贪心的反例

---

一、贪心算法的本质

1.1 什么是贪心？（小白解释）

面试官追问："什么是贪心？为什么叫贪心？"

贪心 = 每一步都选"看起来最好"的选择

为什么叫贪心？
因为它"贪心"——只顾眼前，不考虑全局！

示例：找零钱
面值：1, 5, 10, 20, 50
要凑 63 元

贪心策略：先选最大的
63 → 50 + 13
13 → 10 + 3
3 → 1 + 1 + 1

用了 6 张钞票：50+10+1+1+1

但是！如果面值是 1, 3, 4
要凑 6 元

贪心：4 + 1 + 1 = 3 张
最优：3 + 3 = 2 张 ← 贪心错了！

所以贪心不是万能的！

1.2 什么时候用贪心？（面试核心）

面试官追问："怎么判断一个问题能不能用贪心？"

贪心适用的条件：

1. 有最优子结构
   - 全局最优包含局部最优
   - 每一步的最优选择，能导致全局最优

2. 有贪心选择性质
   - 局部最优能导出全局最优
   - 不需要"回头看"之前的选择

判断方法：
- 如果一道题可以用 DP 解，可能也可以用贪心
- 但能用贪心的题，通常有明显的"最优策略"

举例：
✓ 区间调度：选最早结束的活动，一定最优
✓ 霍夫曼编码：选频率最高的字符用最短编码
✗ 背包问题：选价值/重量比最高的，不一定最优
✗ 最长路径：有环时，不能用贪心

1.3 贪心 vs 动态规划

┌─────────────────────────────────────────────────┐
│                贪心 vs 动态规划                  │
├─────────────────────────────────────────────────┤
│                                                  │
│   贪心：                                          │
│   - 每步只考虑当前最优                           │
│   - 不回溯                                       │
│   - 需要证明局部最优 → 全局最优                   │
│                                                  │
│   动态规划：                                      │
│   - 考虑所有子问题的解                           │
│   - 可能需要回溯                                 │
│   - 一定找到最优解                               │
│                                                  │
│   适用场景：                                      │
│   - 贪心：问题有明显的"最优策略"                │
│   - DP：需要比较多种选择                         │
│                                                  │
└─────────────────────────────────────────────────┘

---

二、区间调度问题

2.1 问题描述

问题：选择最多不重叠的区间

示例：
活动：每个活动有开始时间和结束时间
目标：参加最多不重叠的活动

贪心策略：选最早结束的活动

为什么？
- 最早结束的活动给后面留出最多时间
- 这是显然的最优策略！

2.2 正确性证明（面试加分项）

面试官追问："你能证明为什么选最早结束的是最优的吗？"

证明（交换论证）：

假设最优解是 O = [o1, o2, o3, ...]
贪心解是 G = [g1, g2, g3, ...]

已知 g1 是最早结束的活动

因为 O 中第一个活动一定是某个活动
设为 o1

由于 g1 的结束时间 <= o1 的结束时间
（g1 是最早结束的）

我们可以用 g1 替换 o1，得到新的解 O'
O' 和 O 的活动数量一样多

递归地，我们可以用 g2 替换 O' 中的第二个活动
...

最终可以证明：贪心解和最优解一样优！

这就是"交换论证法"

---

三、经典贪心问题

3.1 跳跃游戏（LeetCode 55）

考察点：贪心判断

问题：能不能跳到数组最后一个位置？

nums[i] = 在位置 i 能跳的最远距离

示例：
nums = [2, 3, 1, 1, 4]

位置 0：能跳到 0+2=2
位置 1：能跳到 1+3=4（能到终点！）
位置 2：能跳到 2+1=3

贪心思路：
维护一个变量：最远能跳到哪里

遍历数组：
- 更新最远距离
- 如果当前位置超出了最远距离 → 跳不到

最终判断：最远距离是否 >= 终点

3.2 无重叠区间（LeetCode 435）

考察点：区间调度的应用

问题：删除最少的区间，使剩余区间不重叠

思路：
- 按结束时间排序
- 贪心地选择结束最早的
- 跳过重叠的区间

为什么对？
因为选择结束最早的，给后面留出最多空间！

---

四、面试总结

贪心算法的核心

┌─────────────────────────────────────────────────┐
│                    贪心算法                       │
├─────────────────────────────────────────────────┤
│                                                  │
│  核心思想：每步选最优，期望全局最优               │
│                                                  │
│  适用条件：                                       │
│  1. 有最优子结构                                 │
│  2. 有贪心选择性质                               │
│                                                  │
│  证明方法：                                       │
│  - 交换论证                                       │
│  - 归纳法                                        │
│                                                  │
│  常见问题：                                       │
│  - 区间调度                                      │
│  - 跳跃游戏                                      │
│  - 霍夫曼编码                                    │
│  - 分数背包                                      │
│                                                  │
└─────────────────────────────────────────────────┘

面试能加分的回答

1. 能判断能不能用贪心
   "如果有明显的最优策略，且能证明局部最优→全局最优"

2. 能证明贪心正确性
   "用交换论证法，证明可以用贪心选择替换"

3. 能区分贪心和 DP
   "当需要比较多种选择时用 DP，当有最优策略时用贪心"

---

相关题目

• LeetCode 55 - 跳跃游戏 - 贪心判断
• LeetCode 435 - 无重叠区间 - 区间调度
• LeetCode 455 - 分发饼干 - 贪心基础