05 贪心
一句话定位:这一讲解决「每一步只做一个小决定,做完全局就是最优」这一类题。
考纲把它单独列出来,是因为它最省时间(代码通常 10 行以内),
也最容易翻车(策略说不清理由就是错的)。
一句话心法:贪心 = 每一步都做「当下最优」的选择,并且能说清「为什么这样选不会吃亏」。
1. 三个必须默写的骨架(每个都带完整代码 + 逐行注释 + 复杂度 + 默写要点)
贪心的代码永远是「先排序(或先定一个扫描顺序),再从左到右做一个固定规则的决定」。
三个骨架的差别只在「排什么」和「每步决定什么」,把这三段背下来,考场上直接套。
骨架 A:排序后一次扫描(局部最优累加)
1 | def skeleton_a(nums): |
- 时间 O(n log n):排序主导,扫描只有 O(n)。
- 空间 O(n):
sorted()返回新列表(原地sort()是 O(log n) 栈空间,但会改调用方的数组,考试时别用)。 - 默写要点:
sorted()有返回值必须接住(sorted(nums)单独一行等于没排);贪心规则写在if里,一眼能看出「每步在决定什么」。 - 最常见的变体:两边都排序 + 双指针(LC 455)。它本质还是骨架 A,只是「累加」变成了「两个下标各往前走」。
骨架 B:区间调度(按右端点排序,能选就选)—— 这是贪心最经典的模型
1 | def skeleton_b(intervals): |
- 时间 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 | def skeleton_c(nums): |
- 时间 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 | def find_content_children(g, s): |
逐行讲解:
| 行 | 代码片段 | 作用 | 为什么这么写 |
|---|---|---|---|
| 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 | def erase_overlap_intervals(intervals): |
逐行讲解:
| 行 | 代码片段 | 作用 | 为什么这么写 |
|---|---|---|---|
| 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 | def max_profit(prices): |
逐行讲解:
| 行 | 代码片段 | 作用 | 为什么这么写 |
|---|---|---|---|
| 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 | 变式1 |
1 | 变式2 |
1 | 变式3 |
