[leetcode] 55. Jump Game

**Jump Game**

**问题描述**

给定一个非负整数数组 `nums`，其中每个元素代表可以跳跃的距离。我们需要判断是否能到达最后一个索引。

**示例1**

输入：`nums = [2,3,1,1,4]`

输出：`true`

解释：我们可以从索引0 跳到索引1、2 或3，接着从索引3 跳到索引4。

**示例2**

输入：`nums = [3,2,1,0,4]`

输出：`false`

解释：我们无法到达最后一个索引，因为我们无法跳过索引3。

**解决方案**

这个问题可以使用贪心算法来解决。我们的目标是找到最长的连续子序列，其长度等于 `nums.length -1`（因为我们需要跳跃到最后一个索引）。

我们维护一个变量 `maxReachableIndex`，表示当前能到达的最大索引。

class Solution:
 def canJump(self, nums: List[int]) -> bool:
 maxReachableIndex =0 for i in range(len(nums)):
 if i > maxReachableIndex:
 return False maxReachableIndex = max(maxReachableIndex, i + nums[i])
 return True

**代码注释**

* 我们首先初始化 `maxReachableIndex` 为0，表示我们可以到达索引0。
* 然后，我们遍历数组 `nums`。对于每个索引 `i`，我们检查是否已经超过了 `maxReachableIndex`。如果是，则意味着我们无法到达当前索引，因此返回 `False`。
* 如果我们可以到达当前索引 `i`，则更新 `maxReachableIndex` 为最大值，即 `max(maxReachableIndex, i + nums[i])`。这表示我们现在可以到达更远的索引。
* 最后，我们检查是否能到达最后一个索引。如果是，则返回 `True`；否则，返回 `False`。

**时间复杂度**

该算法的时间复杂度为 O(n)，其中 n 是数组 `nums` 的长度。我们只需遍历一次数组即可。

**空间复杂度**

该算法的空间复杂度为 O(1)。我们仅使用常数数量的额外空间来存储变量 `maxReachableIndex`。

因此，我们可以有效地解决这个问题，并且时间和空间复杂度都很低。