【贪心算法】 55. 跳跃游戏

55. 跳跃游戏

解题思路

• 定义变量 n 来存储数组 nums 的长度。
• 初始化 farthest 变量为 0，用于记录当前能够到达的最远距离。
• 使用一个 for 循环遍历数组，但是不包括数组的最后一个元素，因为我们的目标是看是否能到达最后一个位置。
• 在循环内部，使用 Math.max(farthest, i + nums[i]) 来更新 farthest，这表示当前能到达的最远距离是之前计算的 farthest 和*当前位置加上当前位置能跳的最远距离中的较大值。
• 如果在某一刻 farthest 小于或等于当前位置 i，意味着无法前进，因此返回 false。
• 循环结束后，如果 farthest 大于或等于数组最后一个位置的索引，表示可以到达最后，返回 true

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int farthest = 0;

        for(int i = 0; i < n - 1; i++){
            farthest = Math.max(farthest,i + nums[i]);// 更新最远的跳跃距离

            if(farthest <= i){
                return false;
            }
        }

        return farthest >= n - 1;// 最大长度大于最后一个位置索引 表示可以到达
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17