Leetcode 跳跃游戏

这段代码解决的是「跳跃游戏」问题，目标是判断是否可以从数组的第一个下标跳到最后一个下标。下面是对代码的详细解释和算法思想的说明：

算法思想：

1. 贪心算法：该算法采用的是贪心思想。我们从数组的第一个元素开始，尝试尽可能往远处跳，并维护一个变量 maxReach 来记录当前能跳到的最远距离。

2. 逐步遍历数组：我们遍历数组中的每个元素，检查当前下标是否能够达到（即 i 是否小于或等于当前的 maxReach）。

3. 更新能跳到的最远距离：对于每个元素，我们更新能跳到的最远位置，即 maxReach，其值为当前的 maxReach 和 i + nums[i] 的最大值。这里的 nums[i] 表示从当前下标 i 能跳跃的最大步数。

4. 无法到达的情况：如果在遍历的过程中，出现 i > maxReach 的情况，意味着当前下标无法到达，返回 false，即无法跳到最后一个下标。

5. 成功到达终点：如果遍历结束时，maxReach 大于等于最后一个下标，返回 true，说明可以成功跳到数组的最后一个下标。

步骤说明：

1. 初始化变量 maxReach 为 0，表示当前能跳到的最远位置是数组的第一个元素。
2. 遍历数组中的每个元素：
   • 如果当前的下标 i 大于 maxReach，说明我们无法跳到这个位置，因此直接返回 false。
   • 否则，更新 maxReach，使其为 maxReach 和 i + nums[i] 的较大值，这样我们就能记录从当前位置可以跳到的最远距离。
3. 遍历结束后，检查 maxReach 是否能够到达或超过数组的最后一个下标。如果是，则返回 true，表示可以跳到最后一个位置；否则，返回 false。

复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次，所以时间复杂度是线性的。
• 空间复杂度：O(1)，只使用了常数个额外的变量。

总结来说，这段代码采用了贪心算法，通过不断更新能跳到的最远距离，来判断是否能够到达数组的最后一个位置。

java 实现代码：

class Solution {public boolean canJump(int[] nums) {int maxReach = 0; //maxReach 是从起点开始最大能达到的下标for(int i = 0; i < nums.length; ++i) {if(i <= maxReach) { //仅当当前位置包含在从起点开始最大能达到的位置之内才更新 maxReachmaxReach = Math.max(maxReach, i + nums[i]); //而 i + nums[i] 是当前位置作为起点能达到的最大下标位置}else {return false;}}return true;}
}