LEETCODE 55. Jump Game 解题思路分析

题目大意：

跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=55

解题思路分析：

由于数组中当前元素代表你在该位置可以跳跃的最大长度，因此为了能够跳到大于等于末尾位置，我们需要找到尽量跳跃长度远的点。初始时，位于index为0的位置，它能跳跃到最远的位置为nums[0]，接下来我们在[1, nums[0]]区间找到一个最大值max，max代表了下一步能跳到的最远距离，如果该距离小于等于nums[0]的话，说明我们在当前可访问区间内任意一点都无法超越nums[0]，则我们一定无法到达终点，返回false。反之，我们能到达的最远处更新为max，此时再在[nums[0] +1,max]范围内找到一个更远的max，重复上述逻辑，直到max大于等于终点位置时，返回true。

实现代码：

public boolean canJump(int[] nums) {
    int maxIndex=nums[0]; // 当前能够跳跃的最远位置
    int current=0; // 当前位置
    // 当最远位置小于终点位置时循环
    while(maxIndex<nums.length-1){
        // 下一步能够跳的最远位置
        int max=maxIndex;
        // 循环当前位置能都跳跃的区间，找到区间内能够到达的最远位置
        for(int i=current+1;i<=maxIndex;i++){
            max=Math.max(max, i+nums[i]);
        }
        // 如果下一步的最远位置不能超越当前位置最远位置，返回false
        if(max==maxIndex) return false;
        // 当前位置更新为原先能到达的最远位置
        current=maxIndex;
        // 最远位置更新为下一步最远位置
        maxIndex=max;
    }
    return true;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 96.88% of Java online submissions for Jump Game.

Memory Usage: 47.2 MB, less than 5.13% of Java online submissions for Jump Game.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-55-jump-game-解题思路分析/