题目描述
思路解析
一句话答案：LeetCode 45 跳跃游戏 II：求从下标 0 到末尾的最少跳数，贪心按每跳能摸到的最远边界分层、走到本层尽头就跳一次，每跳都伸到最远换来最少层数，时间 O(n)、空间 O(1)。
从下标 0 跳到末尾，最少跳几次
nums[i] 是站在下标 i 时最多能往右跳的步数——写着 3，就是往右 1 步到 3 步随你挑。从下标 0 出发，题目保证一定跳得到最后一格，问最少跳几次。题面例子 nums=[2,3,1,1,4]，答案是 2：先落到下标 1，再一步跳到下标 4。
逐格记最少跳数，为什么会到 O(n²)
按定义硬记的话，给每格标一个『到这里最少跳几次』：下标 0 是 0，之后每到一格，回头看前面所有能一步跳到它的格子，挑里面最小的跳数加一。麻烦在每标一格都要往回扫一遍前面的格子，n 格摞起来是 n×n 级比较，数据一大就掉进 O(n²)，操作量随规模翻平方地涨。
不盯具体落点，只盯这一跳能摸到多远
换成贪心来跳，每一步只做当下最划算的选择、不回头。这里最划算的不是『跳到哪个具体格子』，而是让下一跳的落脚范围尽量往右够。道理在于：当前这一跳能落脚的格子里，不管你停在哪一格，决定后面还要跳几次的，只是它们当中谁能摸到最远的下标。既然落哪都不影响，就把这一跳折成一个数——它能延伸到的最远边界。
于是分层来看：第一跳从下标 0 覆盖的一段是第一层，这层里所有格子能摸到的最远处，就是第二跳的右边界、第二层的尽头。走到一层的尽头，就必须再跳一次进下一层。每层都把边界伸到最远，层数压到最少，跳数就最少。
end、farthest、jumps 各盯一件事
落到代码就三个变量：end 是当前这一跳的右边界，farthest 是边扫边探到的、下一跳能达到的最远处，jumps 是已跳次数。从左往右扫，每到一格 i 就用 i+nums[i] 更新 farthest、对整段区间取最大——区间里靠后的某格可能摸得更远。一旦 i 撞上 end，说明这一跳的落脚区间扫完了，jumps 加一，并把 end 推到 farthest 进入下一层。
[2,3,1,1,4] 上手扫一遍，2 跳怎么来的
三个变量都从 0 起。先看下标 0：farthest 取 max(0,0+2)=2；它正好等于 end=0，跳一次让 jumps=1，end 推到 2。到下标 1：farthest 取 max(2,1+3)=4，可还没到 end=2，只更新不跳。到下标 2：farthest 取 max(4,2+1)=4，这次撞上 end=2，再跳一次 jumps=2，end 推到 4。到下标 3：farthest 取 max(4,3+1)=4，没到 end=4，不跳。下标 4 是终点不进循环，扫到下标 3 就收手，返回 jumps=2。
循环边界和落点，一写偏就得多跳
循环若写到最后一格才停，站上终点还会再判一次 i==end、白多跳一回，写成扫到倒数第二格为止才对。撞到 end 时别急着拿 nums[i] 当落点往前挪，贪心要的是整段区间摸到的最远边界 farthest，具体停哪格不影响后面的跳数。farthest 也不能只看当前这一格的 i+nums[i]，得对整段区间一路取最大，区间里更靠后的某格常常伸得更远，漏了 max 就会少算一跳。这套扫法把数组从左到右过一遍、每格做常数次比较，时间 O(n)；只用三个变量、不开数组，空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住三个变量：end = 当前这一跳的右边界，farthest = 当前区间里能摸到的最远处，jumps = 已跳次数。下面每一帧都在套这条规则：扫到 end 就「被迫」跳一次。
一开始 end 指向下标 0（用 r 标），farthest 也是 0，还没跳。注意 farthest 不是「下一步跳到哪」，而是「在当前能落脚的范围内，往前最远能摸到哪个下标」。
处理下标 0：它写着 2，所以从这里最远能摸到下标 0+2=2。把它和之前记的 farthest=0 比一比，取大的 → farthest=2。绿色高亮的就是当前这一跳能摸到的最远位置。
关键时刻：下标 0正好踩在当前这一跳的右边界 end=0 上。说明「当前这一跳能落脚的区间已经扫完」，再往前走就超出这一跳了——所以必须跳一次（jumps=1），并把下一跳的右边界推到刚才记下的 farthest=2。看 r 指针往右跳了一格。
处理下标 1：它写着 3，所以从这里最远能摸到下标 1+3=4。把它和之前记的 farthest=2 比一比，取大的 → farthest=4。绿色高亮的就是当前这一跳能摸到的最远位置。
下标 1还没到当前跳的右边界 end=2（i<end），所以这一格不触发跳跃——它只是帮我们「探路」，把 farthest 顺手更新到 4。跳数保持 1 不变，继续往右。
处理下标 2：它写着 1，所以从这里最远能摸到下标 2+1=3。把它和之前记的 farthest=4 比一比，取大的 → farthest=4。绿色高亮的就是当前这一跳能摸到的最远位置。
关键时刻：下标 2正好踩在当前这一跳的右边界 end=2 上。说明「当前这一跳能落脚的区间已经扫完」，再往前走就超出这一跳了——所以必须跳一次（jumps=2），并把下一跳的右边界推到刚才记下的 farthest=4。看 r 指针往右跳了一格。
处理下标 3：它写着 1，所以从这里最远能摸到下标 3+1=4。把它和之前记的 farthest=4 比一比，取大的 → farthest=4。绿色高亮的就是当前这一跳能摸到的最远位置。
下标 3还没到当前跳的右边界 end=4（i<end），所以这一格不触发跳跃——它只是帮我们「探路」，把 farthest 顺手更新到 4。跳数保持 2 不变，继续往右。
处理下标 4：它写着 4，所以从这里最远能摸到下标 4+4=8。把它和之前记的 farthest=4 比一比，取大的 → farthest=8。绿色高亮的就是当前这一跳能摸到的最远位置。
关键时刻：下标 4正好踩在当前这一跳的右边界 end=4 上。说明「当前这一跳能落脚的区间已经扫完」，再往前走就超出这一跳了——所以必须跳一次（jumps=3），并把下一跳的右边界推到刚才记下的 farthest=8。看 r 指针往右跳了一格。
处理下标 5：它写着 2，所以从这里最远能摸到下标 5+2=7。把它和之前记的 farthest=8 比一比，取大的 → farthest=8。绿色高亮的就是当前这一跳能摸到的最远位置。
下标 5还没到当前跳的右边界 end=8（i<end），所以这一格不触发跳跃——它只是帮我们「探路」，把 farthest 顺手更新到 8。跳数保持 3 不变，继续往右。
处理下标 6：它写着 1，所以从这里最远能摸到下标 6+1=7。把它和之前记的 farthest=8 比一比，取大的 → farthest=8。绿色高亮的就是当前这一跳能摸到的最远位置。
下标 6还没到当前跳的右边界 end=8（i<end），所以这一格不触发跳跃——它只是帮我们「探路」，把 farthest 顺手更新到 8。跳数保持 3 不变，继续往右。
处理下标 7：它写着 3，所以从这里最远能摸到下标 7+3=10。把它和之前记的 farthest=8 比一比，取大的 → farthest=10。绿色高亮的就是当前这一跳能摸到的最远位置。
下标 7还没到当前跳的右边界 end=8（i<end），所以这一格不触发跳跃——它只是帮我们「探路」，把 farthest 顺手更新到 10。跳数保持 3 不变，继续往右。
处理下标 8：它写着 1，所以从这里最远能摸到下标 8+1=9。把它和之前记的 farthest=10 比一比，取大的 → farthest=10。绿色高亮的就是当前这一跳能摸到的最远位置。
关键时刻：下标 8正好踩在当前这一跳的右边界 end=8 上。说明「当前这一跳能落脚的区间已经扫完」，再往前走就超出这一跳了——所以必须跳一次（jumps=4），并把下一跳的右边界推到刚才记下的 farthest=10。看 r 指针往右跳了一格。
处理下标 9：它写着 1，所以从这里最远能摸到下标 9+1=10。把它和之前记的 farthest=10 比一比，取大的 → farthest=10。绿色高亮的就是当前这一跳能摸到的最远位置。
下标 9还没到当前跳的右边界 end=10（i<end），所以这一格不触发跳跃——它只是帮我们「探路」，把 farthest 顺手更新到 10。跳数保持 4 不变，继续往右。
扫描结束，落到终点下标 10。整条路上一共跳了 4 次。注意我们从不在循环里真的「移动落点」，而是用 end/farthest 算清「每一跳的覆盖区间」，扫到边界就跳——这正是贪心给出最少跳数的原因。
边界先想清：只有一格时跳数为 0（已在终点）；题目保证一定可达，所以不必处理「跳不到」的情况。
两个高频追问：贪心正确性可用 BFS 分层理解；end 是当前层右界、farthest 是下一层右界，撞到 end 就进层（跳一次）。
参考代码
def jump(nums): jumps = end = farthest = 0 for i in range(len(nums) - 1): # 最后一格不用再起跳 farthest = max(farthest, i + nums[i]) # 当前区间能摸到的最远 if i == end: # 扫到当前跳的右边界 jumps += 1 # 必须跳一次 end = farthest # 下一跳右边界 = farthest return jumps复杂度
- 时间：O(n)，只把数组从左到右扫一遍，每格做常数次比较
- 空间：O(1)，只用 jumps/end/farthest 三个变量，不开额外数组
易错点
面试追问把动画讲成自己的话
追问为什么这个贪心是对的？怎么直观理解它给出的是「最少」跳数？
追问farthest 和 end 有什么区别？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
加油站
LeetCode 134 · 中等 · 沿着 贪心 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题