跳跃游戏

原题链接

使用的方法

贪心算法

解题思路

• 给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
• 我们可以使用贪心算法来解决这个问题。
• 贪心算法的基本思想是，在每一步选择中都做出当前看起来最好的选择，以期望通过这种方式得到全局最优解。
• 在这个问题中，我们可以维护一个变量 mx，表示当前能够跳跃到的最远位置。我们从数组的第一个位置开始，逐步更新 mx 的值。
• 对于每个位置 i，我们首先检查是否能够到达该位置，即 i 是否小于或等于 mx。如果不能到达该位置，说明我们无法继续前进，直接返回 false。
• 如果能够到达该位置，我们就更新 mx 的值，取当前的 mx 和 i + nums[i] 的最大值。这样，我们就能够知道在当前位置能够跳跃到的最远位置。
• 最后，如果我们能够遍历完整个数组，并且 mx 的值大于或等于数组的最后一个位置，说明我们能够到达最后一个位置，返回 true。否则，返回 false。

代码实现

class Solution {
    public boolean canJump(int[] nums) {
        int mx = 0;
        for(int i=0; i < nums.length; i++){
            if(i > mx) 
                return false;
            mx = Math.max(mx, i + nums[i]);
        }
        return true;
    }
}