企业官网建设流程全解析

LeetCode 55. Jump Game 题解：Go 语言贪心算法判断能否跳到数组末尾

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文基于 LeetCode-Go 仓库中 leetcode/0055.Jump-Game/README.md 的官方题解，结合仓库内对应的 Go 源码实现 与 表驱动测试用例，系统讲解经典贪心问题 Jump Game（跳跃游戏）的题意、核心思路、正确性证明、复杂度分析以及在本地运行测试的完整方法。读完本文，你将掌握"维护最远可达下标"这一贪心套路，并能在 O(n) 时间内解决这类"能否到达终点"的跳跃问题，同时能够独立在本仓库中复现运行结果。

一、题目回顾：非负整数数组上的跳跃判定

原题描述如下：

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

题目大意：给定一个非负整数数组，你最初位于数组的第一个位置（下标 0）。数组中的每个元素代表在该位置最多可以跳跃的长度（可以是 0 到该值之间的任意步数），判断你是否能够到达数组的最后一个位置。

需要特别强调的是两个约束边界：

• 数组元素非负，也就是说每个位置都可能出现0；
• 每个元素表示的是最大跳跃长度，实际跳多少步由你决定，这为贪心策略留下了空间。

仓库题解（leetcode/0055.Jump-Game/README.md）将题意概括为：给出一个非负数组，要求判断从数组 0 下标开始，能否到达数组最后一个位置。

二、示例拆解：两个典型用例

原题给出了两个极具代表性的示例，一个可达、一个不可达，恰好覆盖了贪心判断的两种结果。

示例 1：可以到达末尾

Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

过程说明：位于下标 0 时最大能跳 2 步，选择只跳 1 步到达下标 1；下标 1 处的值为 3，最大可跳 3 步，直接跳到最后一个下标 4，成功到达。

示例 2：无法到达末尾

Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

过程说明：下标 3 处的值为0，也就是说无论之前怎么选择，一旦到达下标 3 就无法继续前进，而它最大只能跳到下标 3 本身（向后无法到达下标 4），因此永远无法到达最后一个位置。

从结构上看，示例 2 是经典的"零值陷阱"：数组中存在一个0，并且这个0之前没有任何位置能够越过它，导致路径被切断。

三、核心解题思路：贪心维护最远可达下标

本题属于经典的贪心问题。仓库题解给出的核心思路可以提炼为三点：

1. 可达范围扩展：如果某一个作为「起跳点」的格子可以跳跃的距离是n，那么表示后面n个格子都可以作为「起跳点」。也就是说，从该格子出发，下标i+1到i+n之间的所有位置都是可达的。
2. 不断更新最远距离：对每一个能作为「起跳点」的格子都尝试跳一次，把「能跳到的最远距离maxJump」不断更新（maxJump = max(maxJump, i + nums[i])）。
3. 断点判断：如果中间有一个下标i比maxJump还要大，说明在这个点和maxJump之间已经"连不上"了，有些点不能到达最后一个位置，直接返回false；如果遍历完整个数组都没有出现这种情况，说明可以一直跳到最后，返回true。

用更直观的话说：我们在遍历数组的同时，始终维护一个"从起点出发、经过已扫描位置能到达的最远下标"。只要当前下标没有超出这个最远可达范围，就说明当前位置是可达的，进而可以用当前位置的跳跃能力继续扩大这个范围。这本质上是一个区间逐步右推的过程，属于典型的贪心（也可视作隐式的区间合并 / BFS 最远层扩展）策略。

四、Go 语言实现：仓库源码逐行解读

仓库中本题的完整实现位于 leetcode/0055.Jump-Game/55.%20Jump%20Game.go，与题解文档中的代码完全一致：

func canJump(nums []int) bool { n := len(nums) if n == 0 { return false } if n == 1 { return true } maxJump := 0 for i, v := range nums { if i > maxJump { return false } maxJump = max(maxJump, i+v) } return true } func max(a int, b int) int { if a > b { return a } return b }

对关键分支与边界条件的解读：

一个值得注意的细节：即使当前位置的值v为 0，只要maxJump已经覆盖了它，程序也不会立即返回false——它只是无法继续扩大可达范围而已，最终结果取决于后续下标是否仍然被覆盖。这与示例 2 中的"零值陷阱"恰好呼应：下标 3 的 0 本身不致命，致命的是没有任何一个之前的位置能跨过下标 3，于是在遍历到下标 4 时发现4 > maxJump(3)，返回false。

此外，仓库中该题代码还附带了同包内独立的max辅助函数（55. Jump Game.go）。由于本题实现位于独立的 leetcode 包内，max与包内其他题目互不冲突。

五、为什么贪心是正确的：不变量与复杂度分析

贪心解法成立的关键在于一个不变量：遍历到下标i时，maxJump恰好等于"从起点出发、仅借助[0, i]范围内位置的可达最远下标"。

• 归纳基础：i = 0时，maxJump = 0，起点可达，成立。
• 归纳递推：若处理完[0, i-1]后maxJump ≥ i，说明i可达；此时用i + nums[i]与旧值取 max，可达范围单调不减，不变量保持。
• 断点判定：一旦出现i > maxJump，说明i不可达，而数组从左到右连续推进，因此之后的所有下标同样不可达，直接返回false正确。

时间复杂度：单次线性扫描，O(n)。空间复杂度：仅使用常数个变量，O(1)。

这也正是该解法能够达到题解文档所述"runtime beats 100%"量级的原因——没有任何多余的分配或二次扫描。

六、测试验证：仓库表驱动测试用例

仓库为本题编写了表驱动（table-driven）测试，位于 leetcode/0055.Jump-Game/55.%20Jump%20Game_test.go，共覆盖 4 组输入输出：

测试通过question55结构体把参数para55{one []int}与期望答案ans55{one bool}打包，循环调用canJump(p.one)后与期望比对，不一致时通过t.Fatalf立即报错并输出实际输入输出，例如：

got := canJump(p.one) if got != a.one { t.Fatalf("input: %v, expected: %v, got: %v", p.one, a.one, got) } fmt.Printf("【input】:%v 【output】:%v\n", p, got)

其中空数组与单元素数组两组用例，正好验证了第四节中n == 0与n == 1两个边界分支的处理逻辑。

七、在本地运行与验证

本仓库使用 Go module 管理依赖（见 go.mod，Go 版本要求 1.19），且项目根目录提供了统一的测试脚本 gotest.sh，其核心命令为：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

针对本题，可在仓库根目录单独运行：

go test -v -run Test_Problem55 ./leetcode/0055.Jump-Game/

运行后可以看到针对四组用例的【input】/【output】输出，以及类似PASS的最终结果。若希望看到单测覆盖率，可加上-cover参数；本项目在根目录执行go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...即可为全部 LeetCode 题解生成统一的覆盖率文件（生成结果写入根目录 coverage.txt）。

八、总结与同类问题联想

Jump Game 是"贪心 + 可达区间"类问题的入门经典，本题的核心套路可以概括为一句话：遍历过程中维护最远可达下标，一旦当前位置超出该范围即宣告不可达。

从源码结构看，本仓库还收录了跳跃类题目的多个变体，例如 45. Jump Game II（最少步数到达末尾）、1306. Jump Game III（从指定起点按值跳跃）、1696. Jump Game VI（带分数的跳跃）等。掌握本题的贪心思想后，阅读这些变体题解将更加轻松。若需继续查阅相关题解，可在仓库的 leetcode 目录下按题号定位对应文件夹，每个题目目录下均包含 README 题解、.go实现与_test.go测试三件套。

要点速览

• 判断标准：能否从下标 0 借助各位置最大跳跃长度到达最后下标；
• 核心变量：maxJump（当前最远可达下标）；
• 终止条件：i > maxJump即不可达；遍历结束则可达；
• 复杂度：时间 O(n)，空间 O(1)；
• 边界：空数组返回false，单元素数组返回true。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go