LeetCode 55. 跳跃游戏

字数 2149 2025-10-26 11:43:54

LeetCode 55. 跳跃游戏

题目描述

给定一个非负整数数组 nums，你最初位于数组的第一个下标（索引为0）。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是判断你是否能够到达最后一个下标。

示例 1:
输入: nums = [2,3,1,1,4]
输出: true
解释: 从索引0跳1步到索引1，再从索引1跳3步到最后一个索引。

示例 2:
输入: nums = [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引3的位置，但该位置的最大跳跃长度是0，所以你永远无法到达最后一个索引。

解题过程

这个问题不要求你找出具体的跳跃路径，只要求判断可行性。因此，我们可以采用一种高效的贪心策略来解决。

核心思路
我们不必模拟每一次跳跃，而是时刻维护一个“当前能够到达的最远位置”，我们称它为 max_reach。只要这个最远位置能够覆盖到数组的最后一个索引，就说明我们可以到达终点。
关键观察
对于数组中的任何一个位置 i，我们能否到达它，取决于在它之前的所有位置中，至少有一个位置 j 满足 j + nums[j] >= i（即从 j 可以一步跳到 i）。
我们的贪心算法就是基于这个观察的优化：我们不需要检查每一个 j，只需要确保我们当前能够到达的最远位置 max_reach 大于等于 i 即可。
算法步骤
让我们一步步遍历数组 nums 的每个索引 i（从0开始）。
- 步骤零：初始化
  定义一个变量 max_reach，表示从起点（索引0）出发，当前能够到达的最远索引。初始时，我们在起点，所以 max_reach = 0 + nums[0]。
- 步骤一：遍历数组
  我们从索引 i = 1 开始遍历，直到倒数第二个元素（即 i < nums.length - 1）。因为我们的目标是到达最后一个索引，如果已经能到达最后一个索引，循环就可以提前结束。
- 步骤二：可行性检查（核心）
  在遍历到每个位置 i 时，我们首先要做一个关键判断：
  “我当前能走到这个位置 i 吗？”
  判断依据就是：如果当前的最大可达距离 max_reach 小于当前位置 i，那就意味着我们根本无法到达 i，更不用说从 i 继续往后跳了。 此时，可以直接得出结论：无法到达终点，返回 false。
- 步骤三：更新最远距离
  如果我们可以到达当前位置 i（即 max_reach >= i），那么我们就从这个新的位置 i 尝试更新“全局最远可达距离”。
  计算从 i 位置能跳到的最远位置：i + nums[i]。
  然后比较 max_reach 和 i + nums[i]，将 max_reach 更新为两者的最大值。
  max_reach = max(max_reach, i + nums[i])
- 步骤四：最终判断
  在遍历过程中，如果 max_reach 已经大于或等于最后一个索引（nums.length - 1），我们可以提前结束循环，返回 true。
  如果遍历顺利结束，我们最后再检查一次 max_reach >= nums.length - 1，并返回结果。
用示例进行推演
我们以示例1 nums = [2, 3, 1, 1, 4] 为例：
- i = 0: 初始化 max_reach = 0 + nums[0] = 2。
- i = 1: 判断 max_reach (2) >= i (1)？是，可以到达位置1。然后更新 max_reach = max(2, 1+3) = max(2,4) = 4。此时 max_reach(4) 已经 >= 最后一个索引(4)，所以提前返回 true。
再以示例2 nums = [3, 2, 1, 0, 4] 为例：
- i = 0: 初始化 max_reach = 0 + 3 = 3。
- i = 1: max_reach(3) >= 1，可到达。更新 max_reach = max(3, 1+2) = 3。
- i = 2: max_reach(3) >= 2，可到达。更新 max_reach = max(3, 2+1) = 3。
- i = 3: max_reach(3) >= 3，可到达。更新 max_reach = max(3, 3+0) = 3。
- i = 4: 现在要判断能否到达位置4。我们在遍历到 i=4 之前，先做步骤二的检查：当前 max_reach 是3，而 i 是4，3 < 4。这意味着我们根本无法走到索引4这个位置。因此，算法在尝试进入 i=4 的循环体之前就会停止（或者在循环判断时发现 i=4 已经大于 max_reach 而提前退出），并返回 false。

总结
这个算法的妙处在于其贪心性质：我们只关心最远能到哪里，而不关心具体路径。时间复杂度是 O(N)，因为只需要遍历一次数组；空间复杂度是 O(1)，只使用了常数级别的额外变量。

LeetCode 55. 跳跃游戏题目描述给定一个非负整数数组 nums ，你最初位于数组的第一个下标（索引为0）。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是判断你是否能够到达最后一个下标。示例 1: 输入: nums = [ 2,3,1,1,4 ] 输出: true 解释: 从索引0跳1步到索引1，再从索引1跳3步到最后一个索引。示例 2: 输入: nums = [ 3,2,1,0,4 ] 输出: false 解释: 无论怎样，你总会到达索引3的位置，但该位置的最大跳跃长度是0，所以你永远无法到达最后一个索引。解题过程这个问题不要求你找出具体的跳跃路径，只要求判断可行性。因此，我们可以采用一种高效的贪心策略来解决。核心思路我们不必模拟每一次跳跃，而是时刻维护一个“当前能够到达的最远位置”，我们称它为 max_reach 。只要这个最远位置能够覆盖到数组的最后一个索引，就说明我们可以到达终点。关键观察对于数组中的任何一个位置 i ，我们能否到达它，取决于在它之前的所有位置中，至少有一个位置 j 满足 j + nums[j] >= i （即从 j 可以一步跳到 i ）。我们的贪心算法就是基于这个观察的优化：我们不需要检查每一个 j ，只需要确保我们当前能够到达的最远位置 max_reach 大于等于 i 即可。算法步骤让我们一步步遍历数组 nums 的每个索引 i （从0开始）。步骤零：初始化定义一个变量 max_reach ，表示从起点（索引0）出发，当前能够到达的最远索引。初始时，我们在起点，所以 max_reach = 0 + nums[0] 。步骤一：遍历数组我们从索引 i = 1 开始遍历，直到倒数第二个元素（即 i < nums.length - 1 ）。因为我们的目标是到达最后一个索引，如果已经能到达最后一个索引，循环就可以提前结束。步骤二：可行性检查（核心）在遍历到每个位置 i 时，我们首先要做一个关键判断： “我当前能走到这个位置 i 吗？” 判断依据就是：如果当前的最大可达距离 max_reach 小于当前位置 i ，那就意味着我们根本无法到达 i ，更不用说从 i 继续往后跳了。此时，可以直接得出结论：无法到达终点，返回 false 。步骤三：更新最远距离如果我们可以到达当前位置 i （即 max_reach >= i ），那么我们就从这个新的位置 i 尝试更新“全局最远可达距离”。计算从 i 位置能跳到的最远位置： i + nums[i] 。然后比较 max_reach 和 i + nums[i] ，将 max_reach 更新为两者的最大值。 max_reach = max(max_reach, i + nums[i]) 步骤四：最终判断在遍历过程中，如果 max_reach 已经大于或等于最后一个索引（ nums.length - 1 ），我们可以提前结束循环，返回 true 。如果遍历顺利结束，我们最后再检查一次 max_reach >= nums.length - 1 ，并返回结果。用示例进行推演我们以示例1 nums = [2, 3, 1, 1, 4] 为例： i = 0 : 初始化 max_reach = 0 + nums[0] = 2 。 i = 1 : 判断 max_reach (2) >= i (1) ？是，可以到达位置1。然后更新 max_reach = max(2, 1+3) = max(2,4) = 4 。此时 max_reach(4) 已经 >= 最后一个索引(4)，所以提前返回 true 。再以示例2 nums = [3, 2, 1, 0, 4] 为例： i = 0 : 初始化 max_reach = 0 + 3 = 3 。 i = 1 : max_reach(3) >= 1 ，可到达。更新 max_reach = max(3, 1+2) = 3 。 i = 2 : max_reach(3) >= 2 ，可到达。更新 max_reach = max(3, 2+1) = 3 。 i = 3 : max_reach(3) >= 3 ，可到达。更新 max_reach = max(3, 3+0) = 3 。 i = 4 : 现在要判断能否到达位置4。我们在遍历到 i=4 之前，先做步骤二的检查：当前 max_reach 是3，而 i 是4， 3 < 4 。这意味着我们根本无法走到索引4这个位置。因此，算法在尝试进入 i=4 的循环体之前就会停止（或者在循环判断时发现 i=4 已经大于 max_reach 而提前退出），并返回 false 。总结这个算法的妙处在于其贪心性质：我们只关心最远能到哪里，而不关心具体路径。时间复杂度是 O(N)，因为只需要遍历一次数组；空间复杂度是 O(1)，只使用了常数级别的额外变量。