Problem: 45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
0 <= j <= nums[i] 且
i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

整体思路

这段代码旨在解决经典的 “跳跃游戏 II” (Jump Game II) 问题。与判断“能否到达”的第一代问题不同，此问题要求在假设总能到达终点的前提下，计算出到达数组最后一个位置所需的 最小跳跃次数。

该算法采用了一种非常高效的 贪心算法，其思想可以类比为 广度优先搜索 (BFS)。它不是关注每一步具体跳到哪里，而是在每一“跳”的范围内，寻找下一“跳”能到达的最远距离。

算法的逻辑步骤如下：

1. 定义边界：

   • 算法使用两个核心变量来定义跳跃的边界：
     • curRight：当前这一跳所能到达的最远边界。可以理解为 BFS 中当前层的右边界。
     • nxtRight：从当前层（0 到 curRight 之间的所有位置）出发，下一跳所能到达的最远边界。
   • ans 变量用于累计跳跃的次数。

2. 贪心遍历：

   • 算法通过一个 for 循环遍历数组。循环的终止条件是 i < nums.length - 1，这一点非常关键，因为我们只需要考虑从倒数第二个位置（或之前）起跳的情况，一旦到达或越过最后一个位置，就不需要再跳了。
   • 在当前跳跃范围内寻找最优的下一步：在循环的每一步（i 从 0 到 curRight），我们都在当前可达的范围内。对于每个位置 i，我们计算从它出发能跳到的最远距离 nums[i] + i。然后，我们用这个值去贪心地更新 nxtRight (nxtRight = Math.max(nxtRight, nums[i] + i))。这确保了 nxtRight 始终记录着从当前这一跳的覆盖范围内，能为下一跳创造的最远落点。
   • 执行跳跃：当循环变量 i 到达了 curRight 的边界时，意味着我们已经遍历完了当前这一跳能到达的所有位置。此时，我们必须执行一次跳跃才能继续前进。
     • if (i == curRight) 这个条件就是“执行跳跃”的触发器。
     • 当触发时，我们将 curRight 更新为 nxtRight，这相当于进入了 BFS 的下一层，设定了新的、更远的可达边界。
     • 同时，我们将跳跃次数 ans 加一。

3. 返回结果：

   • 当循环结束时，ans 中就记录了到达终点所需的最小跳跃次数。

完整代码

class Solution {/*** 计算到达数组最后一个位置所需的最小跳跃次数。* @param nums 数组，每个元素代表在该位置的最大跳跃长度。* @return 最小跳跃次数*/public int jump(int[] nums) {// curRight: 当前这一跳能够到达的最远右边界。int curRight = 0;// nxtRight: 在当前跳跃的覆盖范围内，下一步能够到达的最远右边界。int nxtRight = 0;// ans: 记录跳跃的次数，即结果。int ans = 0;// 遍历数组。循环到倒数第二个元素即可，因为我们的目标是“到达”最后一个位置，// 而不是从最后一个位置起跳。for (int i = 0; i < nums.length - 1; i++) {// 贪心选择：更新下一步能到达的最远距离。// 在当前跳跃的可达范围内（i 从 0 到 curRight），// 我们不断计算从每个位置 i 出发能跳到的最远点 (nums[i] + i)，// 并用它来更新 nxtRight。nxtRight = Math.max(nxtRight, nums[i] + i);// 触发跳跃的条件：当 i 到达了当前跳跃的边界。// 这意味着我们已经考察完了当前这一跳能到达的所有位置，// 必须进行一次新的跳跃才能继续前进。if (i == curRight) {// 更新当前跳跃的边界为下一步能到达的最远边界。curRight = nxtRight;// 跳跃次数加一。ans++;}}// 循环结束后，ans 即为最小跳跃次数。return ans;}
}

时空复杂度

时间复杂度：O(N)

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

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

空间复杂度：O(1)

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

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

参考灵神