贪心算法

2026-06-02

每步选当前看起来最优的，寄希望于全局最优。难点不在写代码，在于证明这一步贪是对的。

贪心的代码通常很短，但正确性证明是灵魂。看起来像贪心的题，一半其实要 DP。

直觉 — 局部最优 → 全局最优的条件

贪心成立有两个隐藏前提，缺一不可：

  1. 贪心选择性质：当前最优的选择，不会断送后面的最优解。
  2. 最优子结构：做完这一步后，剩下的子问题独立、且同样可以贪。

只要任意一步的”看起来最优”会影响后面的可选项，贪心就会翻车，必须退回 DP。判断口诀：能不能构造反例？ 想 1 分钟想不出反例，大概率能贪；想到反例，立刻换 DP。

下面的动画把”按结束时间排序的区间调度”和”反悔贪心装课程”两个最常见的套路串在一起，建议先看一遍再读后面的代码：

三类经典模式

贪心题 90% 落在下面三个模式里，认出模式 → 直接套模板。

1. 区间调度类 — 按结束时间排序

形式：给一堆区间/任务，问最多能选/做多少不冲突的。

关键直觉：早结束的区间留给后面的”空间”最多，所以贪心选最早结束的，永远不亏。证明用 “greedy stays ahead” — 数学归纳，每选完 k 个，贪心的”最后结束时间”都不晚于任意最优解。

变体：开始时间排序（合并区间）、按右端点排序（最少箭射气球）、按左端点排序（合并/插入）。默认先想右端点。

2. 反悔贪心 — 用堆撤回前面的决定

形式：要在某个预算/容量约束下最大化数量或价值。

关键直觉：先无脑贪婪地全装下；一旦超出预算，就从已经装的里面踢掉”最贵的”——堆顶。被踢的那个一定 ≥ 当前这个，所以总代价单调不增，数量却保住了。

经典题：课程表 III、最低加油次数、IPO。识别信号：带 deadline / 容量约束 + 求最多数量。

3. 交换论证类 — 排序的正确性靠”两两交换不变差”

形式：要给一组对象定一个顺序，使某指标最优（如完成时间总和、字典序、罚款最小）。

关键直觉：假设最优解里某两个相邻元素的相对顺序和你的排序不同，证明交换它们不会让答案变差。冒泡式地把”违反贪心”的对全部换掉，得到的还是最优解 — 所以贪心排序就是对的。

典型题：合并果子（小的先合）、皇后游戏（按 排序）、Huffman 编码。

模板 — 区间调度 Python

1
2
3
4
5
6
7
8
def max_intervals(intervals):
    intervals.sort(key=lambda x: x[1])   # 按结束时间
    count, last_end = 0, float('-inf')
    for s, e in intervals:
        if s >= last_end:                # 不重叠
            count += 1
            last_end = e
    return count

复杂度 ，瓶颈在排序。三个变体一行改动：

  • 最少箭射气球：if s > last_end 改成 >，看题目对边界的定义。
  • 无重叠区间数：返回 n - count。
  • 会议室 II（最多并发）：换思路，用最小堆维护当前进行中的会议结束时间。

反悔贪心 — 经典套路与代码

课程表 III：每门课有 ，问最多上几门，规定从 0 时刻开始。

1
2
3
4
5
6
7
8
9
10
11
import heapq

def schedule_courses(courses):
    courses.sort(key=lambda c: c[1])         # 1. 按 deadline 排
    total, heap = 0, []
    for duration, deadline in courses:
        total += duration
        heapq.heappush(heap, -duration)      # 2. 先装进来（最大堆）
        if total > deadline:
            total += heapq.heappop(heap)     # 3. 超了就踢最长的
    return len(heap)

三步走：按截止排 → 无脑装 → 超了就反悔踢最贵。动画的”反悔阶段”演示了堆中最长课程被替换的瞬间。

为什么对：踢掉的那个时长 当前的（否则堆顶不会是它），所以 total 单调不增；同时堆大小保持，永远不亏。

记忆法/易错点

一句话记三类：右端点排（区间）/ 最大堆反悔（容量）/ 两两交换（排序）。

最容易踩的三个坑：

  1. 看起来贪、实际是 DP：经典反例是 0/1 背包 — 按 value/weight 比贪心不对，必须 DP。判断：子问题是否独立？背包里”剩余容量”会被前面的选择改变 → 不独立 → DP。
  2. 排序键选错：区间题排左端点常常错，默认排右端点；按比值排序的题（如 IPO）注意溢出。
  3. 反悔贪心忘了维护 total：每次 push/pop 都要同步更新已用资源，否则下一轮判断会错。

不确定能不能贪？ 三问：（1）有没有反例？（2）子问题独立吗？（3）能不能写出 exchange argument 或 stays-ahead？三个都过 → 放心贪；任一个卡住 → 老老实实写 DP。

思考题

"交换论证"和"贪心始终领先"两种证明方式各适合什么场景？

交换论证适合”排列/排序型”问题——证明某种排序方式最优（按 deadline、按 ratio、按 排）。贪心始终领先适合”选择型”问题——每步选一个元素，证明你的集合在每一步都不比最优差（区间调度、最小生成树）。

为什么反悔贪心要用最大堆？最小堆会怎样？

反悔时踢掉”代价最大”的已选元素，腾出的空间最多，总代价下降最多。换最小堆等于踢掉最便宜的，可能还是超时，并且白白丢了一个”便宜的选择”。最大堆保证每次反悔的边际收益最大。

0/1 背包为什么不能贪心？

按 value/weight 排序贪心的反例：容量 50，物品 (60,10), (100,20), (120,30)，比值依次 6/5/4。贪心选前两个得 160，但最优是后两个 220。原因：选了某个物品后，剩余容量改变，子问题不独立，没有”贪心选择性质”。这种情况必须 DP 枚举所有状态。

LeetCode 练习

热身：455. 分发饼干、122. 买卖股票的最佳时机 II、435. 无重叠区间、55. 跳跃游戏、134. 加油站

进阶：630. 课程表 III、1024. 视频拼接、763. 划分字母区间、502. IPO、871. 最低加油次数