当前位置：首页 > news >正文

【LeetCode 热题 100】55. 跳跃游戏

news 2025/8/18 2:26:41

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

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(1)

整体思路

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

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

算法的逻辑步骤如下：

维护一个“可达范围”：
- 算法使用一个变量 maxLoc 来记录从起点（索引0）出发，通过已经访问过的所有位置，能够到达的最远索引。
- maxLoc 初始化为 0，因为我们最初就站在索引 0 的位置。
遍历与检查：
- 算法通过一个 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])。
  - 这个贪心的选择在于，我们总是希望把我们能到达的边界推得尽可能远。
最终结果：
- 如果循环能够顺利完成（即从未触发 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;}
}