大家好，我是晓星航。今天为大家带来的是 跳跃游戏面试题 相关的讲解！😀

题目简介

题目解答

思路：这样以来，我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置 i，如果它在最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 i+nums[i]更新 最远可以到达的位置。

在遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

解法一：贪心算法＋动态规划

代码：

class Solution {
    public static boolean canJump(int[] nums) {
        if (nums == null) {
            return false;
        }
        //前n-1个元素能够跳到的最远距离
        int k = 0;
        for (int i = 0; i <= k; i++) {
            //第i个元素能够跳到的最远距离
            int temp = i + nums[i];
            //更新最远距离
            k = Math.max(k, temp);
            //如果最远距离已经大于或等于最后一个元素的下标,则说明能跳过去,退出. 减少循环
            if (k >= nums.length - 1) {
                return true;
            }
        }
        //最远距离k不再改变,且没有到末尾元素
        return false;
    }
}

代码注释很好的解释了每一行代码是干嘛的，看不懂的可以参考注释。
这里引入一个话方便大家理解i和k是什么：k好比修路，只要前面一直有修好的路，i(人)就能一直往前走。

复杂度分析：

• 时间复杂度：O(n)，其中n为数组的大小。只需要访问nums数组一遍，共n个位置。
• 空间复杂度：O(1)，不需要额外的空间开销。

题目链接

55. 跳跃游戏
感谢各位读者的阅读，本文章有任何错误都可以在评论区发表你们的意见，我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞，你的每一次鼓励都是作者创作的动力哦！😘