贪心
01 / 共享的机制
每一步取局部最优,并能证明这次提交后续不会被推翻。 没有回溯、没有 DP 表:要么用交换论证说明换掉任意一次贪心都不会更优, 要么用领先论证说明贪心在每个前缀上都不落后。 三个经典子模式把这个想法落成算法:对区间排序后取、在数组上扫描追踪可达边界, 以及在累积量上「一旦失败立即重置起点」。
01 / 一句话本质
油箱在整圈路途上都不能为负。一旦运行油量在某个前缀跌破零,这个前缀里的每个起点都已死 —— 把起点重置到失败点之后。
题目找到一个能走完一圈的起点gas[1, 2, 3, 4, 5]cost[3, 4, 5, 1, 2]
两个长度为 5 的并行数组。每个加油站,diff = gas − cost 注入油箱;油箱不能低于零。
步
0 / 9
i
—
tank
0
start
0
0 / 9
02 / 模式骨架
# 一遍扫描,两个累加器total ← 0; tank ← 0; start ← 0for i in 0..n−1:diff ← gas[i] − cost[i]total += difftank += diffif tank < 0:start ← i + 1 # 这一整段都已死tank ← 0return start if total >= 0 else −1
03 / 什么时候用这个模式
"环形路线,绕一圈"
LC 134 的经典说法。一圈加油站,油箱在
gas[i] 处加油、 在 cost[i] 处消耗,要找一个起点可以一路开回来。把环展平 —— 只要总和 ≥ 0,合法起点一定存在, 重置扫描会把它找出来。"运行和必须非负"
只要题目问「某个累计量是否一直 ≥ 0」—— 余额、燃料、能量、水位 —— 就是这一招:任何使其失败的前缀都不会是合法的起点前缀。
"最大子数组和(Kadane)"
LC 53 是同一套结构,只是把符号翻一下:每当运行和跌破零就把它重置为零, 因为任何把运行和拉成负数的前缀对后面的元素来说都是累赘。 加油站重置的是 start;Kadane 重置的是 sum。证明完全相同。
"最长合法前缀 / 环绕"
输入是环、答案是一段连续弧,而证明能在一次扫描里就排除大量候选起点。 把重置技巧和「整体可行性」一起用就行。
04 / 常见坑
i.
结尾忘了检查
total。少了最后那一行
total >= 0 判断,你可能在根本走不通的输入上也返回一个 start —— 重置总会把它推到某个位置。 总和告诉你「是否存在」合法起点;重置扫描只告诉你「具体是哪一个」。ii.
重置时的差一错误。
i 之后 tank < 0 时,新起点是 i + 1, 不是 i。i 本身也死了:前缀 [start..i] 已经跌破零, 这段里的任何加油站都不可能是合法起点。差一就会重选已死起点 —— 某些输入凑巧也能蒙对,但对抗性的输入下就不行了。iii.
误解证明 —— 真去 O(n²) 枚举每个起点。
学生常常退回到「每个起点都模拟一圈」。关键洞察是一个失败前缀会杀掉里面的每一个起点:若
start..i 跌破零, 那么对任意 j ∈ [start, i],j..i 也是负的 (它是一段已经在负值上的求和的后缀,前面只是少了一段正缓冲)。 这就是模式的全部 —— 一次扫描足够。05 / 去 LeetCode 上练习
四道题,按难度排序。LC 53 是「一段带符号数组上的同一种重置」—— Kadane 还不熟的话,值得先做它。
— / 什么时候用哪个
区间调度
输入是一组区间、问「最多挑出多少个互不重叠」时用。按终点排序后, 每个起点超过已选区间终点的区间就拿。交换论证保证「最早结束」永远安全。
按终点排序 · LC 435 · LC 452
跳跃游戏
每个元素决定你能从这里移动多远时使用。从左到右扫描,维护当前能到达的最远下标; 一旦扫描位置超过这个边界,终点就不可达。
追踪最远 · LC 55 · LC 45
加油站
一段(环形或线性)路径上,某个累积量必须始终非负时用。 一旦运行总和跌破零就把起点重置到下一格 —— 任何使其失败的段都不会是合法起点。
失败即重置 · LC 134 · LC 53