跳跃游戏 II - 贪心算法解法

问题描述：

给定一个长度为 n 的 0 索引整数数组 nums，我们从数组的第一个元素 nums[0] 开始。每个元素 nums[i] 表示从索引 i 可以跳跃的最大长度，换句话说，从位置 i，你可以跳到位置 i + j，其中 0 <= j <= nums[i]，且 i + j < n。

目标是返回到达数组最后一个元素 nums[n - 1] 的 最小跳跃次数。

示例：

示例 1：

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2：

输入: nums = [2,3,0,1,4]
输出: 2

思路分析：

这道题目可以使用 贪心算法 来解决。我们可以理解为：每一步选择跳跃到能够到达的最远位置，直到到达数组的最后一个元素。

解题关键点：

1. 当前跳跃的最远距离：我们在遍历数组时，每次计算当前位置能够跳跃到的最远位置，并更新最远位置。
2. 跳跃次数的增加：当遍历到当前位置的最远位置时，说明需要再进行一次跳跃。跳跃的次数会增加。
3. 贪心选择：每次选择跳跃到当前能到达的最远位置，从而确保跳跃次数最少。

代码解析：

class Solution {public int jump(int[] nums) {int ans = 0;          // 跳跃次数int cur = 0;          // 当前跳跃范围的最远位置int next = 0;         // 下一跳能够到达的最远位置// 遍历数组，直到倒数第二个元素（最后一个元素不需要再跳）for (int i = 0; i < nums.length - 1; i++) {next = Math.max(next, i + nums[i]);  // 更新下一跳能到达的最远位置// 如果已经到达当前跳跃范围的最远位置，则需要增加跳跃次数if (i == cur) {cur = next;  // 更新当前跳跃的最远位置ans++;       // 跳跃次数增加}}return ans;  // 返回跳跃次数}
}

详细讲解：

1. 初始化变量：

   • ans: 记录跳跃次数，初始为 0。
   • cur: 当前跳跃的最远位置，初始为 0（从数组的第一个位置开始）。
   • next: 下一跳能够到达的最远位置，初始为 0。

2. 遍历数组：

   • 我们遍历数组的每个位置，计算从当前位置能跳到的最远位置。
   • next = Math.max(next, i + nums[i]): i + nums[i] 表示从当前索引 i 能跳到的最远位置，我们不断更新 next 为当前能到达的最远位置。

3. 判断是否需要增加跳跃次数：

   • if (i == cur): 当我们遍历到当前位置 i 时，如果 i 正好是当前跳跃的最远位置（即 i == cur），说明我们已经走到了当前跳跃的边界，下一次需要跳跃。
   • cur = next: 更新当前跳跃的最远位置为 next。
   • ans++: 跳跃次数增加。

4. 最终结果：

   • 遍历完成后，ans 就是从 nums[0] 跳到 nums[n-1] 所需的最小跳跃次数。

例子解析：

例子 1：nums = [2, 3, 1, 1, 4]

1. 初始化：ans = 0, cur = 0, next = 0
2. 遍历开始：
   • i = 0：从位置 0 可以跳到 0 + nums[0] = 0 + 2 = 2，所以 next = 2。
   • i == cur (i == 0)：更新 cur = 2，跳跃次数 ans = 1。
   • i = 1：从位置 1 可以跳到 1 + nums[1] = 1 + 3 = 4，所以 next = 4。
   • i == cur (i == 2)：更新 cur = 4，跳跃次数 ans = 2。
   • 跳到最后，跳跃次数为 2。

例子 2：nums = [2, 3, 0, 1, 4]

1. 初始化：ans = 0, cur = 0, next = 0
2. 遍历开始：
   • i = 0：从位置 0 可以跳到 0 + nums[0] = 0 + 2 = 2，所以 next = 2。
   • i == cur (i == 0)：更新 cur = 2，跳跃次数 ans = 1。
   • i = 1：从位置 1 可以跳到 1 + nums[1] = 1 + 3 = 4，所以 next = 4。
   • i == cur (i == 2)：更新 cur = 4，跳跃次数 ans = 2。
   • 跳到最后，跳跃次数为 2。

总结：

• 贪心思想：每次选择跳跃到当前能到达的最远位置，从而保证跳跃次数最少。
• 时间复杂度：O(n)，其中 n 是数组的长度。我们只遍历了一次数组。
• 空间复杂度：O(1)，只使用了常数空间。

这就是 跳跃游戏 II 的贪心算法解法！