一、题目描述
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 10^40 <= nums[i] <= 10^5
二、解题思路
1. 初始化一个变量 maxReach，用来记录当前能够到达的最远索引位置。初始值设为数组的第一个元素，即 nums[0]，因为我们从数组的第一个位置开始。
2. 遍历数组 nums 中的每个元素。对于每个位置 i，执行以下操作：
- 首先，检查
i是否大于maxReach。如果是，这意味着我们无法到达当前位置，因此返回false，因为我们已经无法再向前跳跃了。 - 然后，更新
maxReach。我们将maxReach更新为i + nums[i]和当前maxReach中的较大值。这样做是为了找到从当前位置i出发能够到达的最远位置。 - 接着，检查更新后的
maxReach是否已经大于或等于数组的最后一个下标nums.length - 1。如果是，说明我们可以到达数组的最后一个位置，因此返回true。
3. 如果遍历完整个数组后，maxReach 仍然小于 nums.length - 1，说明我们无法到达数组的最后一个位置，返回 false。
三、具体代码
class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0; // 当前能够到达的最远索引
for (int i = 0; i < nums.length; i++) { // 遍历数组
// 如果当前索引已经超过了最远索引，说明无法到达
if (i > maxReach) {
return false;
}
// 更新最远索引，取当前索引加上可以跳跃的最大长度与当前最远索引的较大值
maxReach = Math.max(maxReach, i + nums[i]);
// 如果最远索引已经超过或等于数组的最后一个下标，说明可以到达末尾
if (maxReach >= nums.length - 1) {
return true;
}
}
// 如果遍历结束，最远索引没有超过数组的长度减一，说明无法到达末尾
return false;
}
}四、时间复杂度和空间复杂度
1. 时间复杂度
- 代码中有一个单层的
for循环，它遍历了整个数组nums一次，没有嵌套的循环或递归调用。 - 在每次迭代中，有一个
Math.max函数调用，这个操作的时间复杂度是 O(1)。 - 因此，整个函数的时间复杂度是 O(n)，其中 n 是数组
nums的长度。
2. 空间复杂度
- 代码中使用了常数个额外变量（
maxReach和i），这些变量的空间需求不随输入数组的大小而变化。 - 没有使用任何额外的数据结构，如数组、列表或哈希表，也没有进行任何递归调用。
- 因此，整个函数的空间复杂度是 O(1)。
五、总结知识点
数组遍历：代码使用了一个
for循环来遍历整个数组nums。这是处理数组或列表数据结构的常见方法。条件判断：在循环中使用了
if语句来进行条件判断。这是控制程序流程的基本结构之一。变量更新：在循环体内部，使用了变量
maxReach来记录遍历过程中能够到达的最远索引。这是动态规划和贪心算法中常用的技巧，用于跟踪最优解的一部分信息。贪心算法思想：这个问题的解决方案采用了贪心算法的思想，即在每一步都做出当前看起来最优的选择，以期望最终得到全局最优解。在这个特定的例子中，每次迭代都尝试更新能够到达的最远位置。
边界条件处理：代码中处理了当当前索引
i超过maxReach时的情况，这是处理边界条件的一个例子。在算法设计中，考虑并正确处理边界条件是非常重要的。数学函数：使用了
Math.max函数来获取两个值中的最大值。这是处理数值比较和计算的常用方法。循环控制：在满足一定条件时，代码通过返回值提前退出循环，这是一种常见的循环控制技巧，可以避免不必要的迭代。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。