贪心
01 / 共享的机制
每一步取局部最优,并能证明这次提交后续不会被推翻。 没有回溯、没有 DP 表:要么用交换论证说明换掉任意一次贪心都不会更优, 要么用领先论证说明贪心在每个前缀上都不落后。 三个经典子模式把这个想法落成算法:对区间排序后取、在数组上扫描追踪可达边界, 以及在累积量上「一旦失败立即重置起点」。
01 / 一句话本质
从左到右扫一遍,只维护目前能到达的最远下标。 不需要枚举每种跳法 —— 一旦扫描位置越过这个边界,终点就不可达; 只要边界先覆盖到最后一格,就已经到达。
题目能否到达最后一格?nums[2, 3, 1, 1, 4]
输入有 5 格。从左到右扫一遍,只维护一个 farthest = 目前能到达的最远下标。
步
0 / 3
i
—
最远
0
0 / 3
02 / 模式骨架
# 扫一次,维护一个最远到达值farthest ← 0for i in 0..n−1:if i > farthest: return False # 扫描跑过了边界farthest ← max(farthest, i + nums[i])if farthest ≥ n − 1: return Truereturn True# 只有一个整数的状态 — 既没 DP 也没递归
03 / 什么时候用这个模式
"能否到达最后一格"
最教科书式的触发词(LC 55)。数组里写的是最大跳跃长度而非精确步数, 所以可达性问题就归约为一次扫描 —— 任何能到达 i 的前缀,都能到达 ≤ i + nums[i] 的任意位置。
"最少跳跃次数"
LC 45。同一组数组,问题不同 —— 可达性已知,要优化次数。 仍是贪心,但要追踪当前边界与下一边界:当
i 越过当前边界时, 确认一次跳跃,并把下一边界接上。同样 O(N),不变式不同。"从某点是否能到达某个值"
LC 1306(Jump Game III)。图不再单调 —— 从下标 i 可以跳到
i + arr[i] 或 i − arr[i]。最远到达技巧不再适用,要退化为带 visited 的 BFS / DFS。"用最少水龙头 / 区间覆盖 [0,n]"
LC 1326。每个水龙头
i 覆盖 [i − r, i + r] —— 形状跟「下标 i 能到达 i + nums[i]」完全一样。 把每个水龙头改写成对应的「最远到达值」,问题立刻变成 LC 45。04 / 常见坑
i.
把可达判定(LC 55)和最少跳跃(LC 45)搞混。
两个都叫「跳跃游戏」,但贪心方式不同。LC 55 只维护一个
farthest, 问有没有掉队。LC 45 要维护两条边界 —— 当前边界(已确认)和下一边界 (当前边界内能跳到的最远)。别把 LC 55 的循环拿来直接数次数。ii.
把
nums[i] 当成「精确跳跃」而非「最大跳跃」。i 处的值是上限 —— 你可以落在
[i+1, i+nums[i]] 中任意位置。 这正是贪心成立的原因:从任何可达的 i 出发,所有更短的跳跃也免费, 所以一个运行最大值就够,不必展开成一棵选择树。iii.
下意识地先想 DP。
DP 也能做(
can[i] = ∃ j<i, can[j] ∧ j+nums[j] ≥ i)—— 但时间 O(N²)、空间 O(N),而贪心是 O(N)、O(1)。任何能塞进内存的输入, DP 检查的事情是一样的,只是更慢。看到「每步上限由当前值决定」就先想扫一遍。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。
— / 什么时候用哪个
区间调度
输入是一组区间、问「最多挑出多少个互不重叠」时用。按终点排序后, 每个起点超过已选区间终点的区间就拿。交换论证保证「最早结束」永远安全。
按终点排序 · LC 435 · LC 452
跳跃游戏
每个元素决定你能从这里移动多远时使用。从左到右扫描,维护当前能到达的最远下标; 一旦扫描位置超过这个边界,终点就不可达。
追踪最远 · LC 55 · LC 45
加油站
一段(环形或线性)路径上,某个累积量必须始终非负时用。 一旦运行总和跌破零就把起点重置到下一格 —— 任何使其失败的段都不会是合法起点。
失败即重置 · LC 134 · LC 53