大家好！我是曾续缘🤖
今天是《LeetCode 热题 100》系列
发车第 79 天
贪心算法第 3 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 10⁴
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]
难度：💖💖

解题方法

初始化变量

下一跳最远可达位置（mx）：在到达必跳位置land之前的所有位置中，我们能到达的最远位置。
下一次必跳位置（land）：如果到达此位置后，再不跳跃就会停滞不前，因此必须进行跳跃，跳至mx位置。
跳跃次数（ans）：记录到达数组末尾所需的最小跳跃次数。

算法步骤

遍历数组，使用一个循环从起始位置开始，直到达到最远可达位置mx。
检查是否已经到达或超过数组末尾，如果是则提前结束循环。
更新最远可达位置mx为当前位置加上从此位置可以跳跃的最大长度与目前mx的较大者。
如果当前位置正好是下一次必跳位置land，说明我们已经衡量完了所有可跳选项，必须进行跳跃。此时，将最远可达位置mx赋值给land，并增加跳跃次数ans，跳跃的具体位置不知道，但是跳跃后最远可达距离是mx，也就是如果后面在到达mx位置后也必须跳了。
当循环结束时，返回总的跳跃次数ans。

Code

查看代码

java

class Solution {
    public int jump(int[] nums) {
        int n = nums.length, mx = 0, land = 0, ans = 0; // 初始化变量
        for(int i = 0; i <= mx; i++){ // 遍历数组
            if(land >= n - 1)break; // 如果已经到达末尾，则结束循环
            mx = Math.max(mx, i + nums[i]); // 更新最远能到达的位置
            if(i == land){ // 不得不跳了
                land = mx; // 跳了后，最远距离确定，如果再次到达最远距离，也是不得不跳
                ans++; // 步数+1
            }
        }
        return ans; // 返回跳跃次数
    }
}

解题方法 ​

初始化变量 ​

算法步骤 ​

Code ​

解题方法

初始化变量

算法步骤

Code