⚖️ 01-数据结构与算法 · 主题 9:贪心¶
贪心 = 每一步都选当前看起来最优的,并证明该策略不亏。 本 notebook 目标:掌握贪心适用判断 → 背熟区间/跳跃/差分三类模板 → 吃透 8 道高频题 → 通过 25 道自测。
前置:主题 8(DP,用于对比)。运行环境:Python 3.8+,无第三方依赖。
核心概念¶
(a) 🗂️ 贪心:三步心法、区间/跳跃/差分模板与证明框架¶
贪心 = 每一步都选当前看起来最优的,并证明这种策略不亏。本 notebook 掌握贪心适用判断,背熟区间、跳跃、差分三类模板,精讲 8 道高频题。
flowchart TB
N1["⚖️ 贪心三步心法"] --> N2["贪心 vs DP:面试必对比"]
N1 --> N3["区间调度:435 / 452"]
N1 --> N4["跳跃游戏:55 / 45"]
N1 --> N5["差分收益:股票 122 / 加油站 134"]
N3 --> N6["分配类:455 / 860"]
N4 --> N7["交换论证:证明框架"]
N5 --> N8["常见 bug 与边界"]
N6 --> N8
N8 --> N9["自测清单"]
- N1 · 贪心三步心法:第一步把问题切成一步步局部决策;第二步每一步按某个"度量"选当前最优(最早结束/最大覆盖/最小成本);第三步用交换论证/归纳法证明局部最优不亏。
- N2 · 贪心 vs DP:面试必对比:两者都在做"当前怎么选择",但贪心不回头看(局部到全局),DP 会存所有子问题的解;能用贪心的题结构通常更简单。
- N3 · 区间调度:按"结束时间最早"排序:无重叠区间 435 数要删几个、最少箭 452 数需要几支箭——同一个贪心思想的两种问法。
- N4 · 跳跃游戏:记录"最远可达范围":55 判断能否到终点;45 求最少跳跃,用"当前步能到达的最远点"计数,一次扫描搞定。
- N5 · 差分收益:股票 II 每天只赚"差价 > 0"的部分(差分收益累加);加油站 134 用"总油量 + 净收益前缀"找起点。
- N6 · 分配类:套路是"小的需求配小的资源":分发饼干先排序再贪心满足;柠檬水找零优先用大面额找零。
- N7 · 交换论证:贪心证明的标准框架:假设最优解里有"相邻两项顺序反了",证明交换后不更差,从而贪心策略就是最优解——面试白板加分项。
- N8 · 常见 bug 与边界:排序关键字选错、贪心策略没证明就硬套、与 DP 的边界模糊导致漏解——每条都要能识别。
- N9 · 自测清单:覆盖区间/跳跃/股票/分配四类高频贪心,L1/L2/L3 分级检验,能现场证明一道题的贪心正确性才算过关。
§1 心智模型与适用判断¶
贪心三步¶
- 分解:把整体问题切成一步步的局部决策
- 选策略:每一步按某个「度量」选当前最优(最早结束/最大覆盖/最小成本)
- 证明:交换论证 / 归纳法说明局部最优不损害全局最优
贪心 vs DP(面试必对比)¶
| 贪心 | DP | |
|---|---|---|
| 决策 | 每步只选一个 | 比较所有子方案 |
| 依赖 | 只依赖上一步 | 依赖多个子状态 |
| 证明 | 需要交换论证 | 转移方程天然正确 |
| 反例代价 | 一步错全错 | 无 |
经典反例:硬币找零 [1,3,4],amount=6:贪心 4+1+1(3 枚)≠ 最优 3+3(2 枚)——贪心不成立时立刻转 DP。
高频贪心模式¶
- 区间类:按右端点/左端点排序(调度、合并、气球)
- 可达类:维护最远覆盖范围(跳跃游戏)
- 差分类:相邻元素收益(股票、加油站)
- 分配类:双指针从小匹配(饼干、孩子)
✍️ §1.1 手算找零:63 分用 [25,10,5,1] 最少几枚?¶
贪心找零:每次拿不超过剩余金额的最大面值——
63手算,验证"最大面值优先"的贪心策略。
设定:硬币面值 [25,10,5,1],金额 63。
| 面值 | 张数 | 剩余 |
|---|---|---|
| 25 | 2(50) | 13 |
| 10 | 1(10) | 3 |
| 5 | 0 | 3 |
| 1 | 3 | 0 |
共 2+1+0+3=6 枚:$63=25\times2+10\times1+1\times3$。
手算收获:
- 贪心正确性靠面值整除性:25 是 10、5、1 的倍数——每步"拿最大面值"不会吃亏;若面值
[1,3,4]金额 6,贪心拿 4+1+1=3 枚但最优 3+3=2 枚 → 贪心会错(§1 适用判断) - 反例是面试必问:"什么情况贪心失效"——答案:局部最优 ≠ 全局最优,需要证明交换论证(本 notebook §6)
- 找零问题本身是"整数背包"特例:贪心 O(币种数) 远快于 DP O(金额×币种);能用贪心就用贪心
- 面试变体:柠檬水找零(860)是"只有 5/10/20 三种币"的贪心——先找 10 再找 5(§5 分配类)
下面 numpy 复算。
# ---- §1.1 验证:numpy 复算贪心找零 ----
coins = [25, 10, 5, 1]
amt = 63
used = []
for c in coins:
k = amt // c
used.append((c, k))
amt -= k * c
total = sum(k for _, k in used)
print(f'63 = {used},共 {total} 枚')
assert total == 6 and amt == 0
print('\n✓ 与手算一致')
§2 区间调度:无重叠区间(435)/ 最少箭(452)¶
435 无重叠区间¶
题目:移除最少区间使剩余互不重叠。
贪心策略:按右端点升序排序,保留「结束最早」的区间——给后面留最大空间:
$$\text{保留} = \max\{\text{不重叠区间数}\}, \quad \text{移除} = n - \text{保留}$$
为什么按右端点(交换论证核心):任何最优解里,第一个区间若换成「结束最早的区间」不产生更多冲突 → 贪心选择可替换进最优解。
452 用最少数量的箭引爆气球¶
等价转换:重叠的气球可以一支箭一起射 → 求最多不相交区间数(按右端点排序,能合并的重叠合并)。
复杂度:$O(n \log n)$(排序主导),$O(1)$。
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ============== 区间调度:435 无重叠区间 / 452 最少箭数 ==============
# 【题目目标】① 435:移除最少区间使剩余区间互不重叠;② 452:用最少的箭引爆
# 所有气球(重叠的气球可共用一箭)
# 【算法思路】区间调度贪心:按右端点升序排序,每次保留「结束最早」的区间,给
# 后面留最大空间;435 的移除数 = n - 最多可保留的不重叠区间数;
# 452 等价于统计不重叠区间数(起点超出当前箭覆盖范围就需要新的一支箭)
# 【变量含义】intervals/points:区间(气球)列表;keep:最多保留区间数;
# end:上一个保留区间的右端点 / 当前这支箭能覆盖的最大右端点;
# arrows:需要的箭数;l/r:区间左右端点
# 【循环不变量】按右端点排序后顺序扫描,end 始终是「最后一个被保留区间 / 当前
# 这支箭」的右端点;end 初始化为 -inf 保证第一个区间必被保留
# 【递归终止】无递归,线性扫描一次即结束
# 【关键边界】435 用 l >= end(端点相接算不重叠);452 用 l > end(端点相接的
# 气球可以共用一支箭)——两个不等号不能混用;end 必须初始化为负无穷
# 【复杂度】O(n log n) 时间(排序主导),O(1) 额外空间
# 435. 无重叠区间:移除最少区间使剩余区间互不重叠
# 贪心思路:按右端点升序排序,每次保留「结束最早」的区间,给后面的区间留最大空间
# 需要移除的个数 = 总区间数 - 最多能保留的不重叠区间数
def erase_overlap_intervals(intervals):
# 移除最少 = n - 最多不重叠数;按右端点升序
intervals.sort(key=lambda x: x[1]) # 按右端点升序排序(结束早的先处理)
keep = 0 # 能保留的不重叠区间个数
end = float('-inf') # 上一个保留区间的右端点,初始负无穷(保证第一个必被保留)
for l, r in intervals: # 遍历每个区间,尝试保留
if l >= end: # 起点不小于上一保留区间的终点 → 不重叠,可保留
keep += 1 # 保留区间数加 1
end = r # 更新当前保留区间的右端点
return len(intervals) - keep # 移除数 = 总区间数 - 最多保留数
# 452. 用最少数量的箭引爆气球:重叠的气球可以共用一支箭
# 等价于求「最多不相交区间数」:按右端点升序,区间起点超过当前箭覆盖范围就要多一支箭
def find_min_arrow_shots(points):
# 排序后统计「新箭」次数 = 不重叠区间数
points.sort(key=lambda x: x[1]) # 按右端点升序排序
arrows = 0 # 需要的箭数
end = float('-inf') # 当前这支箭能覆盖的最大右端点,初始负无穷
for l, r in points: # 遍历每个气球区间
if l > end: # 起点超出当前箭覆盖范围 → 需要新的一支箭
arrows += 1 # 新的一支箭
end = r # 更新当前箭的覆盖右边界
return arrows # 返回最少箭数
print('erase_overlap_intervals:', erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]])) # 1
print('erase_overlap_intervals:', erase_overlap_intervals([[1, 2], [1, 2], [1, 2]])) # 2
print('min_arrow_shots:', find_min_arrow_shots([[10, 16], [2, 8], [1, 6], [7, 12]])) # 2
print('min_arrow_shots:', find_min_arrow_shots([[1, 2], [3, 4], [5, 6]])) # 3
erase_overlap_intervals: 1 erase_overlap_intervals: 2 min_arrow_shots: 2 min_arrow_shots: 3
§3 跳跃游戏(55 / 45):最远可达范围¶
55 判断能否到达终点¶
贪心:维护当前能到达的最远下标:
$$\text{reach} = \max(\text{reach}, i + nums[i]), \quad \text{若 } i > \text{reach} \text{ 则失败}$$
复杂度:$O(n)$ 时间,$O(1)$ 空间。
45 最少跳跃次数¶
贪心:在「当前步可达区间」内挑能扩展最远的点作为下一步:
$$\text{step} \gets \text{step} + 1, \quad \text{当 } i \text{ 触及当前步右界时更新为区间内最大 } i + nums[i]$$
复杂度:$O(n)$,$O(1)$。
# ============== 跳跃游戏:55 可达性 / 45 最少跳跃 ==============
# 【题目目标】① 55:判断能否从下标 0 跳到最后一个下标(每步最多跳 nums[i]);
# ② 45:求到达最后一个下标所需的最少跳跃次数
# 【算法思路】最远可达前缀贪心:55 维护 reach=max(reach, i+nums[i]),任一位置
# i>reach 说明出现不可达断层,直接失败;45 在当前这一步能到达的区间内
# 挑能扩展最远的点作为下一步,扫描触及当前步右边界时步数 +1 并把边界
# 更新为区间内最远可达(每一步都走最优的一跳,次数最少)
# 【变量含义】nums:每格可跳距离;reach:当前能到达的最远下标;i/x:位置与其
# 可跳距离;steps:跳跃次数;cur_end:当前步能到达的右边界;
# farthest:已扫描区间内的最远可达下标
# 【循环不变量】55:位置 [0..i] 全部可达 ⟺ i <= reach(贪心不丢任何可达位置);
# 45:cur_end 恒为当前步覆盖的右边界,farthest 为该区间内最远可能
# 【递归终止】无递归;55 扫完无断层即到达终点;45 只扫描到倒数第二个下标
# (最后一个下标无需再跳)
# 【关键边界】55 必须先判 i>reach 再更新 reach(顺序反了会误判);45 的
# range(n-1) 排除终点;仅在 i==cur_end 边界处才 steps+1 并更新边界
# 【复杂度】两题均为 O(n) 时间、O(1) 空间
# 55. 跳跃游戏:判断能否从起点跳到最后一个下标
# 贪心思路:维护当前能到达的最远下标 reach,只要某个位置 i 超出 reach 就说明出现断层,无法到达终点
def can_jump(nums):
reach = 0 # 当前能到达的最远下标,从 0 开始
for i, x in enumerate(nums): # 遍历每个位置及其可跳距离
if i > reach: # 当前位置已超过最远可达范围 → 无法到达
return False # 当前位置已不可达
reach = max(reach, i + x) # 更新最远可达:从 i 最多能跳到 i+x
return True # 扫描完都没断层 → 可以到达终点
# 45. 跳跃游戏 II:求到达最后一个下标所需的最少跳跃次数
# 贪心思路:在当前这一步能到达的区间内,挑能扩展最远的点作为下一步的起点,触及当前步边界就多跳一次
def jump(nums):
# 最少跳跃次数:每次在可达区间内挑扩展最远的
n = len(nums) # 数组长度
steps = 0 # 跳跃次数
cur_end = 0 # 当前这一步能到达的右边界
farthest = 0 # 已扫描区间内的最远可达
for i in range(n - 1): # 最后一个下标不用跳,只扫描到倒数第二个
farthest = max(farthest, i + nums[i]) # 更新区间内的最远可达
if i == cur_end: # 到达当前步边界:必须再跳一次
steps += 1 # 必须再跳一次
cur_end = farthest # 下一跳的右边界 = 区间内最远可达
return steps # 返回最少跳跃次数
print('can_jump([2,3,1,1,4]) =', can_jump([2, 3, 1, 1, 4])) # True
print('can_jump([3,2,1,0,4]) =', can_jump([3, 2, 1, 0, 4])) # False
print('jump([2,3,1,1,4]) =', jump([2, 3, 1, 1, 4])) # 2
print('jump([2,3,0,1,4]) =', jump([2, 3, 0, 1, 4])) # 2
print('jump([0]) =', jump([0])) # 0
can_jump([2,3,1,1,4]) = True can_jump([3,2,1,0,4]) = False jump([2,3,1,1,4]) = 2 jump([2,3,0,1,4]) = 2 jump([0]) = 0
§3.1 跳跃游戏贪心正确性证明(面试白板)¶
命题:55 的 reach 贪心策略能判定「是否能到终点」。
证明(归纳):令 $\text{reach}_i = \max_{j \le i}(j + nums[j])$ 表示扫描到 $i$ 时可达的最远下标。
- 基例:$i=0$ 时 $\text{reach}_0 = nums[0] \ge 0$,位置 0 本身可达 ✓
- 归纳:若前 $i$ 个位置都可达且 $i \le \text{reach}_{i-1}$,则位置 $i$ 可达;又因为 $i$ 可达,从 $i$ 能跳到的所有位置 $[i, i+nums[i]]$ 也都可达 → $\text{reach}_i \ge \max(\text{reach}_{i-1}, i+nums[i])$ 覆盖了全部可达位置 ✓
- 结论:若某一步 $i > \text{reach}$,说明存在不可达的断层 → 返回 False;否则扫描结束 $\text{reach} \ge n-1$ 即终点可达 ✓
💡 直觉:贪心只需维护「最远可达前缀」,任何可行路径都必须落在该前缀内——所以"最远扩展"不会漏掉任何解(这就是 45 最少步数的贪心依据)。
§4 股票 / 加油站:差分收益¶
122 买卖股票的最佳时机 II(无限次)¶
贪心公式:只累加正收益差:
$$\text{profit} = \sum_i \max(0,\ prices[i+1] - prices[i])$$
为什么对:任意交易序列的总收益等于若干相邻差的组合;每天「上涨就吃、下跌就躲」不会亏。
134 加油站¶
核心公式:
$$\text{剩余}(i) = gas[i] - cost[i], \quad \text{总剩余} < 0 \implies \text{无解}$$
贪心结论:从「累计剩余首次跌到负数」的下一站重新开始——若有解,起点必在该站之后:
$$\text{start} = i + 1 \quad \text{当 } \text{cur\_sum} < 0$$
复杂度:$O(n)$,$O(1)$。
# ============== 差分收益:122 股票 II / 134 加油站 ==============
# 【题目目标】① 122:可无限次交易的股票最大利润;② 134:加油站——判断能否从
# 某个加油站出发绕一圈回到起点,返回起点下标,否则返回 -1
# 【算法思路】差分收益思想:122 只累加正差价 profit += max(0, prices[i]-prices[i-1])
# (上涨就吃、下跌就躲,任意交易序列的总收益等于若干相邻差之和);
# 134 若总剩余(sum(gas)-sum(cost))< 0 说明无解;从累计剩余首次跌到
# 负数的下一站重新作为起点(更早的起点都会在该处失败,故不可能更优)
# 【变量含义】prices:每日价格;profit:累计收益;gas/cost:每站油量与耗油;
# total:全程总剩余油量(全局可行性);cur:当前起点下的累计剩余;
# start:候选起点下标;diff:单站净收益 gas[i]-cost[i]
# 【循环不变量】134:扫描到 i 时若 cur 从未为负,则 0..i 中任意较早起点都可行;
# 一旦 cur<0,起点必在 i+1 之后(区间 [start..i] 内任何点起步到 i 必失败)
# 【递归终止】无递归,一次线性扫描结束
# 【关键边界】122 从第 2 天开始比较(i 从 1 起);134 的 total>=0 才返回 start,
# 否则 -1;cur<0 时 start=i+1 且 cur 归零重新累计
# 【复杂度】两题均为 O(n) 时间、O(1) 空间
# 122. 买卖股票的最佳时机 II(可无限次交易):累加所有「上涨段」的差价
# 贪心原理:每天只要比前一天贵就赚这段差价,即 profit += max(0, prices[i]-prices[i-1])
def max_profit_ii(prices):
# 累加所有上涨段
profit = 0 # 累计收益
for i in range(1, len(prices)): # 从第 2 天开始,与前一天比较
diff = prices[i] - prices[i - 1] # 今天的差价 = 今天价格 - 昨天价格
if diff > 0: # 只有上涨才赚差价(下跌不操作)
profit += diff # 累加这段上涨收益
return profit # 返回总收益
# 134. 加油站:判断能否从某个加油站出发环绕一圈,返回起点下标,否则返回 -1
# 核心结论:若总油量 - 总消耗 < 0 则无解;从累计剩余首次跌到负数的下一站重新作为起点
def can_complete_circuit(gas, cost):
total = 0 # 全程总剩余油量(判断全局可行性)
cur = 0 # 从当前起点出发的累计剩余油量
start = 0 # 候选起点,初始为 0 号加油站
for i in range(len(gas)): # 遍历每个加油站
diff = gas[i] - cost[i] # 到下一站前这一站的净收益
total += diff # 全局可行性
cur += diff # 累计当前候选起点下的剩余油量
if cur < 0: # 剩余为负说明这个起点走不通
start = i + 1 # 起点移到下一站
cur = 0 # 重新累计,从新起点开始
return start if total >= 0 else -1 # 总剩余非负则有解,否则 -1
print('max_profit_ii([7,1,5,3,6,4]) =', max_profit_ii([7, 1, 5, 3, 6, 4])) # 7
print('max_profit_ii([1,2,3,4,5]) =', max_profit_ii([1, 2, 3, 4, 5])) # 4
print('can_complete_circuit([1,2,3,4,5],[3,4,5,1,2]) =',
can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])) # 3
print('can_complete_circuit([2,3,4],[3,4,3]) =',
can_complete_circuit([2, 3, 4], [3, 4, 3])) # -1
max_profit_ii([7,1,5,3,6,4]) = 7 max_profit_ii([1,2,3,4,5]) = 4 can_complete_circuit([1,2,3,4,5],[3,4,5,1,2]) = 3 can_complete_circuit([2,3,4],[3,4,3]) = -1
§5 分配类:分发饼干(455)/ 柠檬水找零(860)¶
455 分发饼干¶
贪心:小胃口吃小饼干——两个数组排序,双指针匹配:
$$\text{满足数} = \#\{i:\ \exists\ g_i \le s_j,\ \text{贪心最小匹配}\}$$
860 柠檬水找零¶
贪心:收到 20 时优先找 10+5(10 元更稀缺,先用掉)——局部最优保全局:
if bill == 20:
if tens > 0 and fives > 0: tens -= 1; fives -= 1
elif fives >= 3: fives -= 3
else: return False
复杂度:均 $O(n \log n)$(455 排序)/$O(n)$(860)。
# ============== 分配类:455 分发饼干 / 860 柠檬水找零 ==============
# 【题目目标】① 455:孩子的胃口数组 g 与饼干大小数组 s,尽量满足更多孩子;
# ② 860:每杯柠檬水 5 元,顾客可能付 5/10/20,判断能否给每位顾客找零
# 【算法思路】小需求配小资源:455 两数组升序排序,双指针从小到大匹配,能喂就喂
# (浪费最小);860 模拟收银:收 20 时优先用 10+5 找零(10 元更稀缺,
# 先用掉),没有 10 元才用 3 张 5 元,凑不齐即失败
# 【变量含义】g/s:孩子胃口与饼干大小数组;i/j:当前孩子/饼干指针;bills:
# 顾客付款序列;fives/tens:手头 5 元与 10 元的数量
# 【循环不变量】455:已满足的前 i 个孩子都用了尽可能小的可行饼干;860:每处理
# 完一位顾客,手中货币守恒且每位顾客均已成功找零
# 【递归终止】无递归;455 当孩子或饼干用尽即停止
# 【关键边界】455 每块饼干只用一次(j 每轮 +1);860 收 10 元必须找 5 元;收 20
# 优先 10+5 而非 3×5(顺序错了会局部失败);fives<0 立即判失败
# 【复杂度】455:O(n log n)(排序主导);860:O(n);空间均 O(1)
# 455. 分发饼干:尽量满足更多孩子,胃口小的孩子用小的饼干去满足
# 思路:孩子胃口和饼干都升序排序,双指针从小到大匹配,能喂就喂
def find_content_children(g, s):
g.sort(); s.sort() # 胃口与饼干大小都升序排序
i = j = 0 # i 指向当前孩子,j 指向当前饼干
while i < len(g) and j < len(s): # 孩子和饼干都没用完
if s[j] >= g[i]: # 当前饼干能满足当前孩子
i += 1 # 满足一个孩子
j += 1 # 饼干只用一次
return i # 被满足的孩子数
# 860. 柠檬水找零:每杯 5 元,顾客可能给 5/10/20,判断能否给每位顾客找零
# 贪心:收 20 时优先用 10+5 找零(10 元更稀缺,先用掉);fives 不够则为失败
def lemonade_change(bills):
fives = tens = 0 # 手头 5 元和 10 元的数量(20 元找零用不上)
for b in bills: # 依次处理每位顾客
if b == 5: # 收 5 元:无需找零
fives += 1 # 5 元增加
elif b == 10: # 收 10 元:需找 5 元
tens += 1 # 10 元增加
fives -= 1 # 找出一张 5 元
else: # 20:优先 10+5
if tens > 0 and fives > 0: # 有 10 元和 5 元 → 先组合找零
tens -= 1
fives -= 1
elif fives >= 3: # 没有 10 元 → 用 3 张 5 元
fives -= 3
else: # 都凑不齐 → 找零失败
return False
if fives < 0: # 5 元不够用 → 失败
return False
return True # 全程都能找零 → 成功
print('find_content_children:', find_content_children([1, 2, 3], [1, 1])) # 1
print('find_content_children:', find_content_children([1, 2], [1, 2, 3])) # 2
print('lemonade_change:', lemonade_change([5, 5, 5, 10, 20])) # True
print('lemonade_change:', lemonade_change([5, 5, 10, 10, 20])) # False(最后 20 找不开)
find_content_children: 1 find_content_children: 2 lemonade_change: True lemonade_change: False
§7 常见 bug 与边界(面试踩坑区)¶
- 排序键选错:区间题按左端点排是常见错误(435 必须按右端点;452 也是右端点)
- 边界相等:435 的
l >= end允许端点相接(不重叠);452 的l > end才射新箭(端点相接可共箭)——两个不等号别搞混 float('-inf')初始化:end 初始用负无穷,否则第一个区间漏判- can_jump 判断顺序:先判
i > reach再更新 reach(顺序反了会误判) - jump 的边界:
range(n - 1)不遍历最后一个(最后一步不用跳) - 柠檬水找零:先找 10+5 还是 3×5——顺序错了会局部失败
- 证明缺失:贪心题只写代码不讲证明,面试官会追问「为什么贪心是对的」
§9 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 题)¶
- 1. 买卖股票的最佳时机 II(LeetCode 122)
- 2. 分发饼干(455)
- 3. 柠檬水找零(860)
- 4. 跳跃游戏(55)
- 5. 跳跃游戏 II(45)
- 6. 最大子数组和(53,贪心/Kadane)
- 7. 分发糖果(135)
- 8. 最长回文串(409,计数贪心)
- 9. 数组拆分 I(561)
- 10. 种花问题(605)
L2 进阶(10 题)¶
- 11. 无重叠区间(435)
- 12. 用最少数量的箭引爆气球(452)
- 13. 加油站(134)
- 14. 合并区间(56,排序贪心)
- 15. 划分字母区间(763)
- 16. 任务调度器(621)
- 17. 会议室 II(253)
- 18. 根据身高重建队列(406)
- 19. 单调递增的数字(738)
- 20. 摆动序列(376)
L3 挑战(5 题)¶
- 21. 重构字符串(767)
- 22. 移掉 K 位数字(402,贪心+栈)
- 23. 分发糖果 II(困难变体)
- 24. 栅栏染色/粉刷房子(树形)
- 25. 砍竹子/切绳子的最大乘积(343,数学贪心)
自测要点¶
- 5 分钟内盲写:122 + 55 + 435
- 能给「区间调度按右端点排序」的交换论证
- 说出贪心 vs DP 的区分标准与一个反例
# ===== 高频补:135 分发糖果 / 738 单调递增的数字 =====
# 【题目目标】① 135:每个孩子至少 1 颗糖,且评分比相邻孩子高的拿得更多,求最小
# 糖果总数;② 738:找不大于 n 的最大整数,其各位数字从左到右单调不减
# 【算法思路】135 两次遍历:左→右保证「比左边评分高就多 1 颗」,右→左保证「比
# 右边评分高就多 1 颗」,每个孩子取两个方向约束的较大值;738 把 n 转成
# 字符列表,找第一个下降点 s[i]>s[i+1],将该位减 1、其后全部改成 9
# (贪心地取最大可行值)
# 【变量含义】ratings:评分数组;n:孩子个数/输入整数;left/right:两次遍历
# 得到的分配数组;s:n 的位字符列表;i:下降点下标;j:后续位
# 【循环不变量】135:left 满足全部左约束、right 满足全部右约束,逐位取 max
# 同时满足两边;738:修改位之前的前缀仍 ≤ 原前缀,保证结果不大于 n
# 【递归终止】无递归;738 扫描结束未发现下降点则原数本身就是答案
# 【关键边界】135 相邻评分相等不强制多分(用 > 而非 >=);738 需处理连续相同位
# (如 332 找到 3>2 后还要向左跳到同值首位一起减 1,得 299);
# 下降点 i+1 之后所有位置 9
# 【复杂度】两者时间均 O(n);135 空间 O(n)(left/right 数组),738 O(1) 额外空间
## §9.5 高频补充:分发糖果(135)/ 单调递增的数字(738)
# 135. 分发糖果:每个孩子至少 1 颗,且评分比相邻高的孩子拿得更多,求最少糖果总数
# 思路:两次遍历——左→右保证「比左边高就多 1 颗」,右→左保证「比右边高就多 1 颗」,逐位取两者较大值
def candy(ratings):
"""135 分发糖果:两次遍历,左→右(比左高则+1),右→左(比右高则取max)。"""
n = len(ratings) # 孩子个数
left = [1] * n # 第一遍(左→右):每个孩子先发 1 颗
for i in range(1, n): # 从左往右遍历
if ratings[i] > ratings[i - 1]: # 当前孩子评分比左边高 → 必须比左边多 1 颗
left[i] = left[i - 1] + 1 # 在左边孩子的基础上加 1
right = [1] * n # 第二遍(右→左):同样先发 1 颗
for i in range(n - 2, -1, -1): # 从右往左遍历
if ratings[i] > ratings[i + 1]: # 当前孩子评分比右边高 → 必须比右边多 1 颗
right[i] = right[i + 1] + 1 # 在右边孩子的基础上加 1
# 每个孩子取两次规则下的较大值,才能同时满足左右两边的约束
return sum(max(left[i], right[i]) for i in range(n))
# 738. 单调递增的数字:找一个不大于 n 的最大整数,其各位数字从左到右单调不减
# 思路:从右往左找第一个「下降点」s[i]>s[i+1],把 s[i] 减 1、其后所有位改成 9(贪心地取最大)
def monotone_increasing_digits(n):
"""738 单调递增的数字:从右往左找第一个 s[i]>s[i+1],该位-1、后面全变9。"""
s = list(str(n)) # 把数字转成字符列表,方便逐位修改
i = 0 # 从最高位开始找下降点
while i < len(s) - 1: # 从左往右扫描相邻两位
if s[i] > s[i + 1]: # 找到第一个「前位大于后位」的下降点
break # 停止扫描,i 就是需要修改的位置
i += 1 # 没发现下降点,继续右移
if i == len(s) - 1: # 一直扫到末尾都没下降 → 本身已满足要求
return n # 本身已单调递增
while i > 0 and s[i - 1] == s[i]:
i -= 1 # 连续相同位一起减(如 332 → 首位也减)
s[i] = str(int(s[i]) - 1) # 把下降点那位减 1(保证不大于 n)
for j in range(i + 1, len(s)): # 下降点之后的每一位
s[j] = '9' # 全部改成 9,使数字尽可能大
return int(''.join(s)) # 拼回整数返回
print('candy([1,0,2]) =', candy([1, 0, 2]), '(期望 5)')
print('candy([1,2,2]) =', candy([1, 2, 2]), '(期望 4)')
print('candy([1,2,87,87,87,2,1]) =', candy([1, 2, 87, 87, 87, 2, 1]), '(期望 13)')
print('monotone_increasing_digits(332) =', monotone_increasing_digits(332), '(期望 299)')
print('monotone_increasing_digits(1234) =', monotone_increasing_digits(1234), '(期望 1234)')
print('monotone_increasing_digits(10) =', monotone_increasing_digits(10), '(期望 9)')
candy([1,0,2]) = 5 (期望 5) candy([1,2,2]) = 4 (期望 4) candy([1,2,87,87,87,2,1]) = 13 (期望 13) monotone_increasing_digits(332) = 299 (期望 299) monotone_increasing_digits(1234) = 1234 (期望 1234) monotone_increasing_digits(10) = 9 (期望 9)