一句话定位:这一讲解决「每一步只做一个小决定,做完全局就是最优」这一类题。
考纲把它单独列出来,是因为它最省时间(代码通常 10 行以内),
也最容易翻车(策略说不清理由就是错的)。
一句话心法:贪心 = 每一步都做「当下最优」的选择,并且能说清「为什么这样选不会吃亏」。

1. 三个必须默写的骨架(每个都带完整代码 + 逐行注释 + 复杂度 + 默写要点)

贪心的代码永远是「先排序(或先定一个扫描顺序),再从左到右做一个固定规则的决定」。
三个骨架的差别只在「排什么」和「每步决定什么」,把这三段背下来,考场上直接套。

骨架 A:排序后一次扫描(局部最优累加)

1
2
3
4
5
6
7
8
9
10
def skeleton_a(nums):
"""骨架 A:排序后一次扫描,边走边把「局部最优」累加进答案。"""
if not nums: # 边界第一行:空数组直接给出答案
return 0
arr = sorted(nums) # 排序:让「最该先处理的元素」排在前面
ans = 0
for v in arr: # 一次扫描,每个元素只被看一次
if v > 0: # 这里的条件就是贪心规则:能拿就拿
ans += v
return ans
  • 时间 O(n log n):排序主导,扫描只有 O(n)。
  • 空间 O(n):sorted() 返回新列表(原地 sort() 是 O(log n) 栈空间,但会改调用方的数组,考试时别用)。
  • 默写要点:sorted() 有返回值必须接住(sorted(nums) 单独一行等于没排);贪心规则写在 if 里,一眼能看出「每步在决定什么」。
  • 最常见的变体:两边都排序 + 双指针(LC 455)。它本质还是骨架 A,只是「累加」变成了「两个下标各往前走」。

骨架 B:区间调度(按右端点排序,能选就选)—— 这是贪心最经典的模型

1
2
3
4
5
6
7
8
9
10
11
12
def skeleton_b(intervals):
"""骨架 B:按右端点排序,能选就选(区间调度模板)。"""
if not intervals: # 空数组:没有区间可处理
return 0
arr = sorted(intervals, key=lambda x: x[1]) # 关键:key 取右端点 x[1]
chosen = 0 # 已经选中的区间个数
last_end = float("-inf") # 上一个选中区间的右端点,-inf 表示还没选过
for start, end in arr: # 元组解包,一行拿到左右两端
if start >= last_end: # 与上一个选中的不重叠 → 选它
chosen += 1
last_end = end # 注意:只有真的选中了才更新边界
return chosen
  • 时间 O(n log n)(排序)+ O(n)(扫描)= O(n log n);空间 O(n)(排序副本)。
  • 默写要点:三处不能错 —— key=lambda x: x[1]、last_end 的初值 float("-inf")、last_end = end 写在 if 里面。

为什么按左端点排序是错的?(这是本讲最容易被追问的一点,必须能当场举反例)

看三个区间:[[0, 10], [1, 2], [3, 4]]。

  • 按左端点排序:顺序还是 [0,10] → [1,2] → [3,4]。贪心选中 [0,10](它左端点最小),
    接着 [1,2] 和 [0,10] 重叠、[3,4] 也和 [0,10] 重叠,一个都选不了 → 只选出 1 个。
  • 按右端点排序:顺序变成 [1,2] → [3,4] → [0,10]。选中 [1,2](右端点 2 最小),
    [3,4] 的 3 ≥ 2 不重叠 → 选;[0,10] 的 0 < 4 重叠 → 不要 → 选出 2 个,这才是最优。
  • 一句话解释:左端点小不等于「占的地方少」([0,10] 就是又早又长),
    而右端点小 = 结束得早 = 给后面留的空间最大。所以区间问题一律按右端点排。

骨架 C:一次遍历记录历史最优(买卖股票型)

1
2
3
4
5
6
7
8
9
10
def skeleton_c(nums):
"""骨架 C:一次遍历,一边用「历史最优」更新答案,一边刷新历史最优。"""
if not nums: # 少于两个元素时按题目要求返回,这里只是示范
return 0
best_history = nums[0] # 历史最优(例如到目前见过的最低价格)
ans = 0
for v in nums[1:]: # 从第二个元素开始,每个都当一次「当前日」
ans = max(ans, v - best_history) # 第一步:用历史最优算今天的候选答案
best_history = min(best_history, v) # 第二步:再决定要不要刷新历史最优
return ans
  • 时间 O(n),空间 O(1):不排序、不开数组,只用了两个变量。
  • 默写要点:两步的先后顺序不能换。必须「先用旧的历史最优算答案,再刷新历史最优」,
    否则会出现「自己减自己」这种不合法的情况(例如同一天既买又卖)。

顺手补 3 个 Python 语法(基础薄弱就先看这张表)

语法 例子 一句话解释
sorted(key=...) sorted(intervals, key=lambda x: x[1]) key 是一个函数,告诉 Python「按每个元素的哪一部分排」;x 就是列表里的一个元素,x[1] 是它的右端点。sorted() 返回新列表,lst.sort() 才是原地改
enumerate for i, v in enumerate(nums): 同时拿到下标 i 和值 v,省掉手写计数器
元组解包 for start, end in intervals: 列表里的每个元素是 [start, end] 这种两项结构时,左边写两个变量就一次拆开,比 x[0]、x[1] 好读也不容易写错
反向排序 sorted(nums, reverse=True) 从大到小;考场上比 key=lambda x: -x 更不容易写错

2. 例题精讲(3 题)

例题 1:分发饼干(LC 455,Easy)

题面:假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;
并且每块饼干 j,都有一个尺寸 s[j]。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i,
这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

  • 示例 1:g = [1,2,3], s = [1,1] → 1(三块胃口的饼干只有 1 和 1,只能满足胃口为 1 的孩子)
  • 示例 2:g = [1,2], s = [1,2,3] → 2(所有孩子都能被满足)
  • 约束:1 <= g.length <= 3 * 10^4;0 <= s.length <= 3 * 10^4;1 <= g[i], s[j] <= 2^31 - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def find_content_children(g, s):
"""LC 455 分发饼干:g 是每个孩子的胃口,s 是每块饼干的大小。

返回最多能满足多少个孩子(每块饼干只能给一个孩子)。
思路:两边都从小到大排序,用最小的饼干去试最小的胃口,
试得动就满足他、两块都往后走;试不动说明这块饼干没用,扔掉换下一块。
"""
if not g or not s: # 没有孩子或没有饼干,一个都满足不了
return 0
kids = sorted(g) # sorted() 返回新列表,不动调用方的 g
cookies = sorted(s)
i = 0 # i 指向「当前还没被满足的最小胃口」
j = 0 # j 指向「当前要用的最小饼干」
while i < len(kids) and j < len(cookies):
if cookies[j] >= kids[i]: # 这块饼干喂得饱这个孩子 → 立刻配对,别再犹豫
i += 1 # 这个孩子已满足,换下一个孩子
j += 1 # 无论喂饱没喂饱,这块饼干都消耗掉了
return i # i 正好等于「被满足的孩子数」

逐行讲解:

行 代码片段 作用 为什么这么写
1 def find_content_children(g, s): 函数签名 参数名沿用题目给的 g/s,考卷上一眼看懂
2–6 三引号 docstring 说明参数含义和返回值 纸上也留一行注释写清返回什么,避免和「返回剩余饼干数」搞混
7–8 if not g or not s: / return 0 空数组保护 s 可能是空列表;not [] 为 True,两个都判省事
9–10 kids = sorted(g) / cookies = sorted(s) 两边各自升序 必须用 sorted() 接住返回值;写 sorted(g) 单独一行等于白排
11 i = 0 指向最小胃口的孩子 用 i 同时当「已满足人数」,省掉一个计数器变量
12 j = 0 指向最小的饼干 j 只会往前走,不会回头 → 总循环次数是 O(n + m)
13 while i < len(kids) and j < len(cookies): 双指针循环 两个条件缺一不可:孩子走完了或饼干用完了都得停
14 if cookies[j] >= kids[i]: 判断能否满足 因为都排好序了,cookies[j] 就是「手里最小且还没用的饼干」
15 i += 1 满足了一个孩子 写在 if 里面:配不上就不能把孩子的指针往前推
16 j += 1 饼干用掉 写在 if 外面:配不上也说明这块饼干太小,留着没用,直接扔
17 return i 返回结果 i 从 0 开始,每满足一个加 1,天然就是答案;不用再写 count

走查(人脑跑一遍,纸上写完必做):

用例 轮次 i j cookies[j] vs kids[i] 动作 结果
普通:g=[1,2,3], s=[1,1] 第 1 轮 0 0 1 >= 1 ✅ i→1, j→1 继续
第 2 轮 1 1 1 >= 2 ❌ j→2 继续
第 3 轮 1 2 j 到界,退出 — 1 ✅
边界:g=[1,2], s=[1,2,3] 第 1 轮 0 0 1 >= 1 ✅ i→1, j→1 继续
第 2 轮 1 1 2 >= 2 ✅ i→2, j→2 i 到界,退出 → 2 ✅
极端:g=[10], s=[5,5,5] 3 轮 0 0/1/2 5 >= 10 ❌ ×3 每轮 j+1 j 到界 → 0 ✅

复杂度:时间 O(n log n + m log m) —— 排序是瓶颈,扫描最多走 n + m 步且每步 O(1)。
空间 O(n + m) —— 两份排序副本;如果面试官要求 O(1) 额外空间,
可以口头说「原地 sort() 数组本身、只开两个指针」,但要先确认能不能改输入。

题面:给定一个区间的集合 intervals,其中 intervals[i] = [start_i, end_i]。
返回需要移除区间的最小数量,使剩余区间互不重叠。
注意:区间 [1,2] 和 [2,3] 的端点相接,算不重叠;可以认为区间的终点总是大于它的起点。

  • 示例 1:intervals = [[1,2],[2,3],[3,4],[1,3]] → 1(移除 [1,3] 后剩下三个区间互不重叠)
  • 示例 2:intervals = [[1,2],[1,2],[1,2]] → 2(留下 1 个,移除 2 个)
  • 示例 3:intervals = [[1,2],[2,3]] → 0(端点相接,本来就不重叠)
  • 约束:1 <= intervals.length <= 10^5;intervals[i].length == 2;-5 * 10^4 <= start_i < end_i <= 5 * 10^4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def erase_overlap_intervals(intervals):
"""LC 435 无重叠区间:返回最少需要移除多少个区间,使剩下的区间互不重叠。

思路:按右端点从小到大排序,能留就留。留的标准是
「当前区间的左端点 >= 上一个留下的区间的右端点」。
"""
if not intervals: # 空数组无区间可移除
return 0
ivs = sorted(intervals, key=lambda x: x[1]) # key 取右端点 x[1],不是左端点 x[0]
keep = 0 # 已经留下来的区间个数
end = float("-inf") # 上一个留下的区间的右端点,-inf 表示还没留过
for start, stop in ivs: # 元组解包:一行取出左右两端
if start >= end: # 和上一个留下的区间不重叠 → 留下它
keep += 1
end = stop # 只有真的留下了,才更新边界
return len(ivs) - keep # 总数减去留下的,就是要移除的

逐行讲解:

行 代码片段 作用 为什么这么写
1 def erase_overlap_intervals(intervals): 函数签名 参数名直接用题目的 intervals
2–6 docstring 说明返回「最少移除数」 防止把「留下数」当答案交上去
7–8 if not intervals: / return 0 空数组保护 空集合不用移除任何区间
9 ivs = sorted(intervals, key=lambda x: x[1]) 按右端点升序 全题最关键的一行;写 x[0] 就错了(见 §2 的反例)
10 keep = 0 留下的区间个数 用「留下几个」倒推「移除几个」,比直接数移除更顺
11 end = float("-inf") 上一个留下区间的右端点 用负无穷当哨兵,第一个区间必然满足 start >= end,不用特判 keep == 0
12 for start, stop in ivs: 遍历 + 元组解包 左边两个变量一次拆开 [start, end];右端点特意命名成 stop 而不是 end,避免和循环外那个记录边界的 end 变量撞名(撞了会把它改掉,答案就错了)。等价写法 for x in ivs: start, stop = x[0], x[1] 更长也更易错
13 if start >= end: 判断是否重叠 用 >= 而不是 >:题目明确说 [1,2] 和 [2,3] 不重叠
14 keep += 1 留下这个区间 能留就留:右端点已经最小,留它不会挡住后面
15 end = stop 更新边界 必须在 if 里面;写在 if 外面会让「被移除的区间」也更新边界,答案偏大
16 return len(ivs) - keep 返回最少移除数 总数减去留下数,才是题目要的「移除数」

走查(把每个区间按右端点排序后的取舍过程完整列出来):

用例 排序后的顺序 轮次 start vs end 决定 keep 结果
普通:[[1,2],[2,3],[3,4],[1,3]] [1,2],[2,3],[1,3],[3,4] 1 1 >= -inf ✅ 留下 [1,2],end=2 1
2 2 >= 2 ✅ 留下 [2,3],end=3 2
3 1 >= 3 ❌ 移除 [1,3] 2
4 3 >= 3 ✅ 留下 [3,4],end=4 3 4 − 3 = 1 ✅
边界:[[1,2],[1,2],[1,2]] 三个右端点都是 2 1 1 >= -inf ✅ 留下第 1 个 1
2 1 >= 2 ❌ 移除 1
3 1 >= 2 ❌ 移除 1 3 − 1 = 2 ✅
极端:[[1,100],[2,3],[4,5]] [2,3],[4,5],[1,100] 1 2 >= -inf ✅ 留下 [2,3],end=3 1
2 4 >= 3 ✅ 留下 [4,5],end=5 2
3 1 >= 5 ❌ 移除长区间 [1,100] 2 3 − 2 = 1 ✅

注意极端用例:[1,100] 左端点最小、看起来「最早」,
按右端点排序后它排在最后并被移除——这正是「按左端点排是错的」的现场演示。

复杂度:时间 O(n log n) —— 排序 O(n log n),扫描 n 次每次 O(1)。
空间 O(n) —— sorted() 生成的副本;不算副本的话额外空间是 O(1)(只有 keep、end、循环变量)。

例题 3:买卖股票的最佳时机(LC 121,Easy)

题面:给定一个数组 prices,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票,并选择在未来的某一个不同的日子卖出该股票。
设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。
如果你不能获取任何利润,返回 0。

  • 示例 1:prices = [7,1,5,3,6,4] → 5(第 2 天买、第 5 天卖,6 - 1 = 5)
  • 示例 2:prices = [7,6,4,3,1] → 0(一路下跌,不交易最赚)
  • 约束:1 <= prices.length <= 10^5;0 <= prices[i] <= 10^4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def max_profit(prices):
"""LC 121 买卖股票的最佳时机:只能买一次、卖一次,且卖出在买入之后。

返回最大利润,赚不到钱返回 0。
思路:从左往右走,一边记录「到目前见过的最低价格」,
一边用「今天的价格 - 历史最低价」更新答案。一次遍历就够。
"""
if not prices or len(prices) < 2: # 少于两天无法完成一次买卖
return 0
min_price = prices[0] # 历史最低价,初始化为第一天的价格
best = 0 # 最大利润,初始化为 0(当天买当天卖=不赚不亏)
for p in prices[1:]: # 从第 2 天开始,把每天都当成「卖出日」试一遍
profit = p - min_price # 假设今天卖出,能赚多少
if profit > best: # 先用「今天之前的最低价」算利润
best = profit
if p < min_price: # 再考虑今天能不能刷新历史最低价
min_price = p
return best

逐行讲解:

行 代码片段 作用 为什么这么写
1 def max_profit(prices): 函数签名 参数名沿用题目
2–6 docstring 说明返回最大利润、赚不到返回 0 提醒自己答案的初值是 0 而不是负无穷
7–8 if not prices or len(prices) < 2: / return 0 空数组和只有一天的保护 两个条件写一起:len(prices) < 2 已经覆盖空数组,但显式写 not prices 更保险、更好读
9 min_price = prices[0] 历史最低价初值 初值必须用第一天的价格,不能用 0(价格可以是 0,用 0 会让「历史最低」失去意义,也会让 best 恒为 0)
10 best = 0 答案初值 初值是 0:一路下跌时循环里 profit > best 永不成立,正好返回题目要的 0,不用额外处理
11 for p in prices[1:]: 从第 2 天开始遍历 第 1 天不可能卖出(没有买点),从下标 1 开始,顺便避免「自己减自己」
12 profit = p - min_price 今天的候选利润 min_price 此刻还是「今天之前」的最低价 —— 顺序是关键
13–14 if profit > best: / best = profit 更新答案 等价于 best = max(best, profit),手写 if 在纸上更不容易错
15–16 if p < min_price: / min_price = p 刷新历史最低价 必须在这之后才刷新:若先刷新,今天跌到最低时会算出 p - p = 0,看似无害,但逻辑上已经是「同一天买卖」,换个题面就错了
17 return best 返回答案 遍历结束 best 就是全局最大利润

走查:

用例 天 p 历史最低 min_price profit best 结果
普通:[7,1,5,3,6,4] 1(初值) — 7 — 0
2 1 7 1−7 = −6 0 刷新 min_price=1
3 5 1 4 4
4 3 1 2 4
5 6 1 5 5
6 4 1 3 5 5 ✅
边界:[7,6,4,3,1] 5 天 6/4/3/1 一路刷新为 1 全为负 0 0 ✅
边界:[] / [5] — — — — 0 第 7 行直接 return 0 ✅

复杂度:时间 O(n) —— 循环执行 n − 1 次,每次常数次比较和减法。
空间 O(1) —— 只用了 min_price、best、p、profit 四个变量。

3. 变式练习(3 题)

变式 1 · LC 122 买卖股票的最佳时机 II(Medium)

  • 题面摘要:prices[i] 是第 i 天股价。可以无限次买入和卖出(但不能同一天既买又卖,也可以完全不交易),
    返回能获取的最大利润。示例:[7,1,5,3,6,4] → 7(第 2 天买第 3 天卖赚 4,第 4 天买第 5 天卖赚 3);[1,2,3,4,5] → 4。
  • 关键提示:先想「如果明天比今天贵,我应不应该今天买」。再想一步关键性质:
    一次 1→5 的交易(赚 4)和 1→2、2→3、3→4、4→5 四段各赚 1 加起来利润完全一样,
    所以「拆成每一对相邻两天单独看」不会亏。想清楚「下坡要不要动」。
    注意这是一个一次遍历、不需要排序的题(对应骨架 C 的思路)。
  • 对应函数:max_profit_ii(prices)
  • 自查:[7,1,5,3,6,4] → 7;[1,2,3,4,5] → 4;[7,6,4,3,1] → 0;[] → 0。

变式 2 · LC 605 种花问题(Easy)

  • 题面摘要:flowerbed 是只含 0 和 1 的数组,1 表示已种花、0 表示空位,花不能种在相邻位置。
    问能否在不违反规则的前提下再种下 n 朵花。示例:[1,0,0,0,1], n=1 → true;同数组 n=2 → false。
  • 关键提示:从左到右扫,遇到空位就问两件事——「左边能不能种」(i == 0 或者是 0)
    和「右边能不能种」(i == len-1 或者是 0)。能种就种(这就是贪心:早种不会让后面更差)。
    两个最容易错的点:一是边界 i == 0 和 i == len(flowerbed) - 1 必须单独放行,不然会访问越界或误判;
    二是种下之后要把这一位改成 1,这样后面相邻的位置自然就种不了了,不用额外写逻辑。
    这题不需要排序,是「一次扫描 + 就地标记」的骨架 A 变体。
  • 对应函数:can_place_flowers(flowerbed, n)
  • 自查:[1,0,0,0,1],1 → True;[1,0,0,0,1],2 → False;[0],1 → True;[0,0,0],2 → True;[1],0 → True。

变式 3 · LC 1005 K 次取反后最大化的数组和(Easy)

  • 题面摘要:给你整数数组 nums 和整数 k,可以恰好选择某个下标并将 nums[i] 变成 -nums[i],
    一共做 k 次(同一下标可以重复选),返回数组可能的最大和。
    示例:[4,2,3], k=1 → 5;[3,-1,0,2], k=3 → 6;[2,-3,-1,5,-4], k=2 → 13。
  • 关键提示:先排序(对应骨架 A)。排序之后负数都排在前面、而且绝对值最大的负数最靠前,
    所以「从左往右,遇到负数就翻,翻一次扣一次 k」就是最优的——把最亏的负数变成正数,收益最大。
    剩下 k 还有的三种情况要逐个想清楚:k 用完(什么都不做);k 是偶数(翻同一个数偶数次等于没翻,白翻);
    k 是奇数(必须花掉这最后一次,那就翻绝对值最小的那个数,损失最小)。
    「恰好 k 次」是这题的陷阱,别写成「最多 k 次」。
  • 对应函数:largest_sum_after_k_negations(nums, k)
  • 自查:[4,2,3],1 → 5;[3,-1,0,2],3 → 6;[2,-3,-1,5,-4],2 → 13;[-1],999999 → 1。
1
2
3
4
5
6
7
8
9
10
变式1
def max_profit_ii(prices):
"""LC 122:可以无限次买卖,求最大利润。"""
if not prices or len(prices) < 2:
return 0
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]: # 今天比昨天贵
profit += prices[i] - prices[i - 1] # 吃这段差价
return profit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
变式2
def can_place_flowers(flowerbed, n):
"""LC 605:能否再种下 n 朵花。"""
count = 0
length = len(flowerbed)

for i in range(length):
# 当前是空位
if flowerbed[i] == 0:
# 左边能不能种:i==0 是边界,或左边是 0
left_ok = (i == 0) or (flowerbed[i - 1] == 0)
# 右边能不能种:i==length-1 是边界,或右边是 0
right_ok = (i == length - 1) or (flowerbed[i + 1] == 0)

if left_ok and right_ok:
flowerbed[i] = 1 # 就地标记:种下
count += 1
if count >= n: # 提前返回,不用扫完
return True

return count >= n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
变式3
def largest_sum_after_k_negations(nums, k):
"""LC 1005:恰好 k 次取反后最大化的数组和。"""
nums.sort() # 排序:负数在前,绝对值大的负数最靠前

# 第一步:从左往右,遇到负数就翻,扣 k
for i in range(len(nums)):
if k > 0 and nums[i] < 0:
nums[i] = -nums[i]
k -= 1

# 第二步:处理剩下的 k
if k % 2 == 1: # k 还剩奇数,必须再翻一次
# 翻绝对值最小的那个数,损失最小
min_idx = nums.index(min(nums)) # 找到最小值的下标
nums[min_idx] = -nums[min_idx]

return sum(nums)