Problem: 55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

整体思路

这段代码旨在解决经典的 “跳跃游戏” (Jump Game) 问题。问题要求判断给定一个非负整数数组，你是否能够从第一个索引（位置0）开始，最终到达数组的最后一个索引。数组中的每个元素代表你在该位置可以跳跃的最大长度。

该算法采用了一种非常高效且直观的 贪心算法 (Greedy Algorithm)。其核心思想不是去模拟每一步具体的跳跃，而是去维护一个当前可到达的最远距离。

算法的逻辑步骤如下：

1. 维护一个“可达范围”：

   • 算法使用一个变量 maxLoc 来记录从起点（索引0）出发，通过已经访问过的所有位置，能够到达的最远索引。
   • maxLoc 初始化为 0，因为我们最初就站在索引 0 的位置。

2. 遍历与检查：

   • 算法通过一个 for 循环，从左到右遍历数组的每一个位置 i。
   • 核心检查（可达性判断）：在循环的每一步，首先检查当前位置 i 是否在之前计算出的 maxLoc 的覆盖范围之内。即 if (i > maxLoc)。
     • 如果 i > maxLoc，这意味着当前位置 i 根本无法从任何前面的位置跳跃到达。就好像河流中间断了一截，我们永远也到不了对岸。在这种情况下，我们不可能到达数组的末尾，因此直接返回 false。
   • 贪心更新（扩展范围）：如果当前位置 i 是可达的，我们就利用这个位置的跳跃能力来尝试扩展我们的“可达范围”。
     • 从位置 i 出发，最远可以跳到 i + nums[i]。
     • 我们将这个新的可达距离与已知的最远距离 maxLoc 进行比较，并更新 maxLoc 为两者中的较大值。即 maxLoc = Math.max(maxLoc, i + nums[i])。
     • 这个贪心的选择在于，我们总是希望把我们能到达的边界推得尽可能远。

3. 最终结果：

   • 如果循环能够顺利完成（即从未触发 i > maxLoc 的条件），这意味着数组的每一个位置（包括最后一个位置 n-1）都在我们的可达范围之内。
   • 因此，只要循环能走完，就说明最后一个位置是可达的，返回 true。

完整代码

class Solution {/*** 判断是否能从数组的第一个位置跳到最后一个位置。* @param nums 数组，每个元素代表在该位置的最大跳跃长度。* @return 如果可以到达最后一个位置，则返回 true，否则返回 false。*/public boolean canJump(int[] nums) {int n = nums.length;// maxLoc: 记录从起点出发，当前能够到达的最远位置的索引。// 这是一个贪心选择，我们总是希望这个值越大越好。int maxLoc = 0;// 遍历数组的每一个位置，i 代表当前位置的索引。for (int i = 0; i < n; i++) {// 核心判断：检查当前位置 i 是否可达。// 如果当前位置 i 已经超出了之前所有位置能够到达的最远距离 maxLoc，// 说明 i 这个位置是无论如何也无法到达的，因此直接返回 false。if (i > maxLoc) {return false;}// 贪心更新：更新能够到达的最远位置。// 从当前位置 i 出发，最远可以跳到 i + nums[i]。// 我们取这个新值与已知的最远位置 maxLoc 中的较大者，作为新的最远可达距离。maxLoc = Math.max(maxLoc, i + nums[i]);// 一个小优化：如果 maxLoc 已经能覆盖或超过最后一个位置，就可以提前结束了。// if (maxLoc >= n - 1) {//     return true;// }}// 如果循环能够顺利完成，意味着数组的最后一个位置（n-1）也是可达的// (因为它没有在 if (i > maxLoc) 中被拦截)，因此返回 true。return true;}
}

时空复杂度

时间复杂度：O(N)

1. 循环：算法的核心是一个 for 循环，它从 i = 0 遍历到 n-1。这个循环最多执行 N 次，其中 N 是 nums 数组的长度。
2. 循环内部操作：
   • 在循环的每一次迭代中，执行的都是基本的比较、加法和 Math.max 操作。
   • 这些操作的时间复杂度都是 O(1)。

综合分析：
算法由 N 次 O(1) 的操作组成。因此，总的时间复杂度是 N * O(1) = O(N)。

空间复杂度：O(1)

1. 主要存储开销：算法只使用了几个固定数量的整型变量（n, maxLoc, i）。
2. 空间大小：这些变量的数量不随输入数组 nums 的大小 N 而改变。

综合分析：
算法没有使用任何与输入规模 N 成比例的额外数据结构（如新数组或哈希表）。因此，其额外辅助空间复杂度为 O(1)。

参考灵神