055 跳跃游戏

🔗 相关链接

跳跃游戏

📜 题目描述

给定一个非负整数数组 nums，最初位于数组的第一个下标。数组中的每个元素代表在该位置可以跳跃的最大长度。

🎯 目标

判断是否能够到达最后一个下标。如果可以，返回 true；否则，返回 false。

📊 示例

示例 1

输入：

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

输出：

true

解释：
可以先跳 1 步，从下标 0 到达下标 1，然后再从下标 1 跳 3 步到达最后一个下标。

---

示例 2

输入：

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

输出：

false

解释：
无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0，因此永远不可能到达最后一个下标。

📝 提示

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

💡 思路

贪心

维护一个与 nums 等长的布尔数组，表示每个元素是否可达。遍历一遍 nums，根据 nums 的值将对应布尔数组的区间更新为 true，遍历完成后返回布尔数组最后一个元素的值。若中间可更新区间超过了数组长度末尾，则直接返回 true。

💻 代码实现

public boolean canJump(int[] nums) {
    boolean[] arr = new boolean[nums.length];
    arr[0] = true;
    for (int i = 0; i < nums.length; i++) {
        if (!arr[i]) {
            continue;
        }
        int range = nums[i];
        if (i + range >= nums.length - 1) {
            return true;
        }
        for (int j = i; j <= Math.min(i + range, nums.length - 1); j++) {
            arr[j] = true;
        }
    }
    return arr[nums.length - 1];
}