好的，我们接下来讲解 LeetCode 第 55 题：跳跃游戏。

题目描述

给定一个非负整数数组 nums，你最初位于数组的 第一个下标。数组中的每个元素代表你在该位置可以跳跃的 最大长度。

你的目标是判断你是否能够从第一个下标出发，到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步从下标 0 到下标 1，然后再跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标 3 的位置。但该位置的最大跳跃长度是 0，所以永远不可能到达最后一个下标。

解题过程循序渐进讲解

步骤 1：理解问题核心

这个问题不是要你找出跳多少步，而是问 是否可能到达。
关键在于：对于当前能到达的最远位置，我们在这个范围内可以不断尝试扩展最远能到达的位置。

步骤 2：贪心思路的引入

我们可以维护一个变量 farthest，表示 从起点经过若干步能到达的最远下标。
遍历数组时，如果当前位置 i 在 farthest 范围内，说明能到达 i，那么就可以从 i 再跳 nums[i] 步，从而可能更新 farthest。

如果遍历过程中 farthest 已经大于等于最后一个下标，就返回 true。
如果遍历到某个 i 时，i > farthest，说明无法到达 i，更无法到达终点，返回 false。

步骤 3：算法步骤详细描述

1. 初始化 farthest = 0（因为起点是下标 0，所以最初能到达的最远位置是 0）。
2. 遍历数组下标 i，从 0 到 n-1：
   • 如果 i > farthest，说明无法到达当前位置，直接返回 false。
   • 否则，用 i + nums[i] 更新 farthest：
     farthest = max(farthest, i + nums[i])
   • 如果 farthest >= n-1，说明可以到达最后一个下标，返回 true。
3. 如果遍历结束，返回 farthest >= n-1 的结果（实际上如果中途没返回 true，这里就是 false）。

步骤 4：用示例推导

示例 1： nums = [2,3,1,1,4]

• i=0：farthest=0，i=0 可到达，更新 farthest = max(0, 0+2) = 2
• i=1：1 <= 2 可到达，更新 farthest = max(2, 1+3) = 4，此时 4 >= 4（最后一个下标），返回 true

示例 2： nums = [3,2,1,0,4]

• i=0：farthest=0，可到达，更新 farthest = max(0, 0+3) = 3
• i=1：1 <= 3，可到达，更新 farthest = max(3, 1+2) = 3
• i=2：2 <= 3，可到达，更新 farthest = max(3, 2+1) = 3
• i=3：3 <= 3，可到达，更新 farthest = max(3, 3+0) = 3
• i=4：4 > 3，无法到达 i=4，返回 false

步骤 5：为什么贪心有效？

我们不需要知道具体跳到哪里，只需要知道最远能覆盖到哪里。
只要最远能覆盖的位置大于等于终点，就说明能到达。
如果在某个位置 i 发现 i 已经超过了当前能覆盖的最远位置，说明中间断掉了，无法继续前进。

这种方法时间复杂度 O(n)，空间复杂度 O(1)。

总结

跳跃游戏（能否到达版本）的核心是维护一个 最远可到达位置，遍历数组时不断更新它，并检查是否能覆盖到终点或是否出现无法覆盖的断点。这是一种典型的贪心算法，高效且直观。