面试官最爱问的‘贪心算法’：从LeetCode真题到避坑指南，一次讲透

面试官最爱问的‘贪心算法’：从LeetCode真题到避坑指南，一次讲透

在技术面试中，贪心算法（Greedy Algorithms）几乎是必考知识点。无论是应届生还是初级工程师，面对LeetCode上那些看似简单却暗藏玄机的贪心题目时，常常陷入“思路对了但证明不了正确性”或“误用贪心导致全盘皆输”的困境。本文将带你从面试官视角拆解贪心算法的核心套路，结合高频真题（如跳跃游戏、分发糖果、无重叠区间等），揭秘贪心策略的适用条件、正确性证明技巧，以及那些容易踩坑的经典反例。

1. 贪心算法的本质与面试考察点

贪心算法的核心思想是局部最优导致全局最优。与动态规划不同，贪心算法不会回溯之前的决策，而是在每一步选择当前看起来最优的解。这种特性使得它在某些问题上极其高效，但也意味着并非所有问题都适用。

面试官最关注的三个维度：

• 问题识别：能否判断一个问题是否适合贪心策略
• 正确性证明：如何严谨地证明贪心选择的正确性
• 边界处理：对特殊情况的考虑是否全面

注意：贪心算法在面试中常与动态规划对比考察，比如背包问题中0-1背包（动态规划）与分数背包（贪心）的区别。

2. 贪心算法的经典应用场景

2.1 区间调度问题

LeetCode 435（无重叠区间）的贪心解法：

def eraseOverlapIntervals(intervals): 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

关键点：选择最早结束的区间可以为后续留下更多选择空间。

2.2 分配问题

LeetCode 135（分发糖果）的双向贪心策略：

1. 从左到右遍历，保证右边评分更高的孩子比左边多
2. 从右到左遍历，保证左边评分更高的孩子比右边多

2.3 跳跃游戏

LeetCode 55（跳跃游戏）的贪心判断：

def canJump(nums): max_reach = 0 for i in range(len(nums)): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) return True

3. 贪心算法的正确性证明方法

3.1 交换论证法

通过假设存在一个更优解，然后通过交换元素证明贪心解不会更差。例如在区间调度问题中：

1. 假设存在一个比贪心解更大的兼容区间集合
2. 用贪心选择的区间替换第一个不同的区间
3. 证明新集合仍然兼容且大小不变

3.2 归纳法

证明贪心选择在每一步都保持最优子结构：

• 基础情况：初始状态满足条件
• 归纳步骤：假设前k步正确，证明第k+步选择仍最优

3.3 贪心选择性质

证明局部最优选择能导致全局最优解。例如霍夫曼编码中，每次合并频率最低的两个节点能保证总编码长度最短。

4. 贪心算法的常见陷阱与反例

4.1 0-1背包问题

贪心策略（按价值/重量比排序）会失效的例子：

背包容量W=50时：

• 贪心解：A+B（总价值160）
• 最优解：B+C（总价值220）

4.2 最短路径问题

Dijkstra算法是贪心算法的成功案例，但在负权边情况下会失效：

A --3--> B -- (-2) --> C \ / \--1--> D --1-/

从A到C的最短路径应为A->D->C（总权重2），但Dijkstra会选择A->B->C（总权重1，错误）

5. 面试实战技巧

5.1 快速识别贪心问题

当问题具有以下特征时可考虑贪心：

• 具有贪心选择性质
• 无后效性（当前决策不影响后续子问题）
• 子问题独立

5.2 解题模板

1. 将问题转化为一系列选择步骤
2. 定义什么是“局部最优”
3. 证明贪心选择的正确性
4. 处理边界条件

5.3 高频题目分类

在实际面试中，遇到新题时可以先思考：“如果我只考虑眼前最优，会不会导致全局最优？”如果答案是肯定的，再结合数学归纳或反证法验证思路的正确性。