💥 两行“跳步”代码，凭什么敢不回头？
先看两段“看起来不太对、但确实对”的代码：
# LC.55 跳跃游戏：一趟扫描，从不回头max_reach=0fori,xinenumerate(nums):ifi>max_reach:returnFalse# ← 凭什么这里失败就整体失败了？max_reach=max(max_reach,i+x)# LC.134 加油站：跌破0就把起点跳到i+1，永不回头foriinrange(n):tank+=gas[i]-cost[i]iftank<0:start=i+1# ← 凭什么0..i里没有一站能做起点？tank=0这两行代码是贪心里最典型的“跳步”：不是逐个验证候选，而是一次排除一大片。它们的正确性不靠直觉，靠两件东西：
- 跳跃游戏：可达集合永远是一个连续前缀
[0, maxReach]——这是“决策包容性”； - 加油站：从a出发在b处跌破0，则a…b之间任何一站都到不了b——这是“冗余候选的批量排除”。
今天的目标就是把这两句话从“感觉”变成“证明”。
📦 题目速览（30秒读懂）
题目1：跳跃游戏（LC.55）
非负整数数组
nums，每个元素代表最大跳跃长度。从下标0出发，判断能否到达最后一个下标。示例：
[2,3,1,1,4]→true；[3,2,1,0,4]→false
约束：n ≤ 1e4。
题目2：加油站（LC.134）
环形路线，
gas[i]是第i站油量，cost[i]是到下一站的耗油。从某站出发（油箱为空），能否绕一圈？返回起点编号或-1（保证解唯一）。示例：
gas=[1,2,3,4,5], cost=[3,4,5,1,2]→ 输出3
约束：n ≤ 1e5。
🧠 核心思路
一、跳跃游戏：覆盖范围贪心
核心洞察：题目说“可以跳最多nums[i]步”，意味着可以跳任意不超过它的步数。因此：
从已可达的任意位置出发，能覆盖到的下标集合，永远是一个连续区间
[0, maxReach]。
这意味着“当前能到哪些位置”不需要布尔数组，只需要一个整数maxReach。
算法：
maxReach = 0 for i in 0..n-1: if i > maxReach: return False # 断层：i 不可达 → 后面全不可达 maxReach = max(maxReach, i + nums[i]) if maxReach >= n-1: return True # 提前成功 return True为什么i > maxReach就能直接判否？（反证）
- 循环不变量：扫描到
i之前，maxReach= 从0..i-1中任一可达位置出发能到的最远下标。 - 若
i > maxReach，则所有j < i都满足j + nums[j] <= maxReach < i。 - 跳跃只能向右，要到达
i或更远，最后一步必然从某个j < i跳过来。 - 但所有
j < i都够不着i→i及之后全部不可达 → 直接返回False。∎
这就是“决策包容性”：一个标量maxReach包容了所有历史决策的信息。
与DP对比
DP解法：dp[i] = 能否到达i，转移是OR_{j<i}(dp[j] && j+nums[j] >= i)，O(n²)时间O(n)空间。
贪心更优的原因：可达集合恒为连续前缀，整个dp[]布尔数组的信息量坍缩成一个整数。DP内层求的max可以增量维护，O(n²)塌成O(n)。实测n=10,000时快2,549倍，空间从O(n)降到O(1)。
二、加油站：两步走 + 两个证明
第一步（充要条件）：sum(gas) >= sum(cost)⟺ 有解。
- 必要性：总油量不够显然无解。
- 充分性：见下方前缀和证明。
第二步（一次遍历定起点）：从0出发累加diff[i] = gas[i] - cost[i]，一旦tank < 0，就把起点设为i+1并清空tank，绝不回头验证。
为什么跌破0可以直接跳到i+1？（引理 + 反证）
引理：若从a出发，走到b时油量首次跌破0，则a..b之间任何一站都不能作为起点。
证明：
- 设从
a出发到达中间站c（a < c <= b）时，油箱剩余T >= 0。 - 路线A：从
a开到c，油箱有T升，继续往b开。 - 路线B：从
c作起点，油箱是0升（题目规定出发为空），继续往b开。 - 两条路线从
c到b路况完全相同，唯一区别是路线A多带了T >= 0升油。 - 既然路线A都过不去
b，少带油的路线B只会更早趴窝。
一句话：从中间站出发，等于丢掉了前面攒下的余量，只会更差不会更好。
为什么sum(gas) >= sum(cost)就一定有解？（前缀和证明）
记号：A(i) = Σ_{k=0}^{i} (gas[k] - cost[k])，A(-1)=0。
引理A：贪心输出的start满足A(start-1) = min{A(-1), A(0), ..., A(n-1)}，即全局最小前缀和的位置。
定理：若total = A(n-1) >= 0，则从start出发可跑完一圈。
证明：从start出发到任意站j的累计剩余油量：
- 若
j >= start：剩余 =A(j) - A(start-1)。因A(start-1)是全局最小，所以>= 0✅ - 若
j < start（已绕回）：剩余 =A(j) + total - A(start-1)。同理>= 0✅
全程非负 → 跑完一圈。∎
附加收获：解的唯一性（start = argmin(A) + 1）；total < 0时返回-1。
🖼️ 图解算法（手把手走一遍）
跳跃游戏：[2,3,1,1,4]（可达）
| i | nums[i] | i > maxReach? | maxReach更新 | 可达区间 |
|---|---|---|---|---|
| 0 | 2 | 否 | max(0, 0+2)=2 | [0,2] |
| 1 | 3 | 否 | max(2, 1+3)=4 | [0,4]≥ n-1 →true |
跳跃游戏：[3,2,1,0,4]（不可达）
| i | nums[i] | i > maxReach? | maxReach | 说明 |
|---|---|---|---|---|
| 0 | 3 | 否 | 3 | 覆盖[0,3] |
| 1 | 2 | 否 | 3 | 没扩展 |
| 2 | 1 | 否 | 3 | 没扩展 |
| 3 | 0 | 否 | 3 | 死点 |
| 4 | 4 | 4 > 3 ✅ | — | 断层！return False |
加油站：gas=[1,2,3,4,5], cost=[3,4,5,1,2]
diff = [-2,-2,-2,3,3]，总和 = 0 ≥ 0 → 必有解。
| i | diff | tank累加 | 跌破? | start |
|---|---|---|---|---|
| 0 | −2 | −2 | ✅ | 1 |
| 1 | −2 | −2 | ✅ | 2 |
| 2 | −2 | −2 | ✅ | 3 |
| 3 | +3 | 3 | 否 | 3 |
| 4 | +3 | 6 | 否 | 3 |
答案 = 3✅
💻 代码实现（Python + Java）
Python版
classSolution:# ============ LC.55 跳跃游戏 ============defcanJump(self,nums:List[int])->bool:max_reach=0fori,xinenumerate(nums):ifi>max_reach:returnFalsemax_reach=max(max_reach,i+x)ifmax_reach>=len(nums)-1:returnTruereturnTrue# ============ LC.45 跳跃游戏 II（分层贪心） ============defjump(self,nums:List[int])->int:iflen(nums)<=1:return0jumps,cur_end,farthest=0,0,0foriinrange(len(nums)-1):farthest=max(farthest,i+nums[i])ifi==cur_end:jumps+=1cur_end=farthestifcur_end>=len(nums)-1:breakreturnjumps# ============ LC.134 加油站 ============defcanCompleteCircuit(self,gas:List[int],cost:List[int])->int:total=tank=start=0foriinrange(len(gas)):diff=gas[i]-cost[i]total+=diff tank+=diffiftank<0:start=i+1tank=0return-1iftotal<0elsestartJava 版
classJumpGameSolution{publicbooleancanJump(int[]nums){intmaxReach=0;for(inti=0;i<nums.length;i++){if(i>maxReach)returnfalse;maxReach=Math.max(maxReach,i+nums[i]);if(maxReach>=nums.length-1)returntrue;}returntrue;}}classGasStationSolution{publicintcanCompleteCircuit(int[]gas,int[]cost){inttotal=0,tank=0,start=0;for(inti=0;i<gas.length;i++){intdiff=gas[i]-cost[i];total+=diff;tank+=diff;if(tank<0){start=i+1;tank=0;}}returntotal<0?-1:start;}}⚠️防坑提醒：
- 跳跃游戏：
maxReach更新必须在i > maxReach判定之后。- LC.45循环
i < n-1，不含最后一个元素。- 加油站：
total和tank是两个独立量，别合并。
实测数据（本机运行）
贪心 vs DP（跳跃游戏，结果一致）：
| n | 贪心 | DP（O(n²)） | 提速 |
|---|---|---|---|
| 5,000 | 0.000013s | 0.247s | 19,405× |
| 10,000 | 0.000839s | 2.138s | 2,549× |
| 100,000 | 0.0086s | 无法跑 | — |
贪心 vs 暴力（加油站，最坏情况）：
| n | 贪心 | 暴力 O(n²) | 提速 |
|---|---|---|---|
| 2,000 | 0.000106s | 0.172s | 1,619× |
| 4,000 | 0.000195s | 0.688s | 3,520× |
⏱️ 复杂度分析（面试必问）
| 题目 | 贪心 | DP/暴力 |
|---|---|---|
| LC.55 跳跃游戏 | O(n) / O(1) | O(n²) / O(n) |
| LC.45 跳跃游戏 II | O(n) / O(1) | — |
| LC.134 加油站 | O(n) / O(1) | O(n²) / O(1) |
🚀 举一反三：6 道高频变体题
| 题目 | 变化 | 思路要点 |
|---|---|---|
| LC.45 跳跃游戏II | 求最少跳跃次数 | 分层贪心：curEnd/farthest |
| LC.1306 跳跃游戏III | 可双向跳 | 变成图遍历（BFS/DFS + visited） |
| LC.1024 视频拼接 | 片段覆盖[0,T] | 按start排序 + 覆盖范围贪心 |
| LC.1326 灌溉花园 | 水龙头覆盖全段 | 区间覆盖贪心 |
| LC.435 无重叠区间 | 取舍类 | 按end升序 + 交换论证 |
| LC.452 引爆气球 | 最少箭穿透 | 同骨架，>代替>= |
💬 面试追问模拟（提前准备，惊艳全场）
Q1：跳跃游戏的DP解法怎么写？为什么贪心更优？
DP：
dp[i] = 能否到达i，转移OR_{j<i}(dp[j] && j+nums[j] >= i)，O(n²) / O(n)。贪心更优因为可达集合恒为连续前缀，整个布尔数组坍缩成一个整数。实测快 2,549 倍。
Q2：加油站为什么跌破0就跳到i+1？
引理：若从
a出发在b处跌破0，则a..b中任何一站c都不能作起点。
因为从a开到c时还有T >= 0余量，而从c作起点时油箱是0——两条路线在c之后路况相同，但路线B少带了T升油，只会更早趴窝。
Q3：贪心和DP的边界在哪？
判据：局部最优能否推出全局最优，且你能写出证明。写得出交换论证/包容性/前缀和 → 贪心；写不出 → DP。
三条信号：
① DP 状态能压缩成可增量维护的标量 → 可退化贪心；
② 决策有后效性 → 必须DP；
③ 要求输出方案 → 回溯。
🧩 实战小技巧（刷题党必备）
- 口诀：跳跃看覆盖，一路不回头；加油跌破零，起点跳i+1。
- 模板：覆盖范围贪心 = 维护一个标量边界；加油站 = total判有解 + tank定位点。
- 防坑：
maxReach更新顺序；LC.45循环i < n-1；total与tank别混。
📈 实际应用场景（不止是刷题）
- 游戏关卡：判断能否通关、最少步数
- 资源调度：油箱问题、补给站规划
- 网络路由：覆盖范围转发
- 视频拼接：最少片段覆盖完整时间轴
🎁 今日思考题
如果把加油站改成“求所有可行起点”，算法怎么改？
提示：题目保证最多一个解，所以total >= 0时直接返回start即可；若允许多个解，需要找出前缀和A的所有全局最小值位置——想想为什么“全局最小值”和“可行起点”是一回事。
