55. 跳跃游戏

📝 题目描述

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

---

📌 示例

示例 1

输入：

nums = [2,3,1,1,4]

输出：

true

解释：从下标 0 跳 1 步到 1，再从 1 跳 3 步到终点。

示例 2

输入：

nums = [3,2,1,0,4]

输出：

false

解释：到达下标 3 后，最大跳跃长度为 0，无法到达终点。

---

🚀 最优解：贪心算法（跟踪最远可达范围）

🔍 思路解析

核心逻辑：持续跟踪当前能到达的最远索引，若遍历过程中最远索引无法覆盖当前位置，则说明无法到达终点；若最远索引覆盖了终点，则直接返回true。

1. 初始化maxReach为0（初始能到达的最远索引）；
2. 遍历数组每个位置i：
   • 若当前位置i超过了maxReach，说明无法到达该位置，直接返回false；
   • 更新maxReach为max(maxReach, i + nums[i])（当前位置能跳到的最远索引）；
   • 若maxReach已覆盖终点（>= nums.length - 1），提前返回true。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read the array
        String input = scanner.nextLine();
        input = input.substring(1, input.length() - 1); // Remove brackets
        String[] numsStr = input.split(",");

        int[] nums = new int[numsStr.length];
        for (int i = 0; i < numsStr.length; i++) {
            nums[i] = Integer.parseInt(numsStr[i].trim());
        }

        Solution solution = new Solution();
        boolean result = solution.canJump(nums);

        System.out.println(result);
        scanner.close();
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        int ans = 0;
        for(int i = 0; i < nums.length && i <= ans; i++) {
            ans = Math.max(ans, i + nums[i]);
        }
        return ans >= nums.length - 1;
    }
}

---

🧠 通俗易懂解释

可以把问题理解为“拓展可达区域”：

• 从起点出发，能到达的区域是0~nums[0]，记录这个区域的最远边界maxReach；
• 遍历这个区域内的每个位置，每个位置都会拓展新的可达区域（比如位置i能拓展到i+nums[i]）；
• 若遍历到某个位置时，该位置不在当前可达区域内（i > maxReach），说明无法到达；
• 若拓展后的区域覆盖了终点，直接判定“能到达”。

以示例2 nums = [3,2,1,0,4] 为例：

1. i=0：maxReach = max(0, 0+3)=3，未覆盖终点（4）；
2. i=1：maxReach = max(3, 1+2)=3；
3. i=2：maxReach = max(3, 2+1)=3；
4. i=3：maxReach = max(3, 3+0)=3；
5. i=4：i=4 > maxReach=3，返回false（正确）。

---

⏱ 时间复杂度

O(n)

仅遍历数组一次，每个元素的计算为常数时间，效率最优。

---

💾 空间复杂度

O(1)

仅使用一个变量，无额外空间消耗。

---

不断更新能够跳到的最远的地方