题目描述

给定一个长度为 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]。

代码

public int jump(int[] nums) {
    // 初始化边界和最大位置
    int end = 0;
    int maxPosition = 0; 
    int steps = 0;
    
    // 遍历数组的每一个元素，但不包括最后一个元素
    for(int i = 0; i < nums.length - 1; i++) {
        // 更新能跳到的最远位置
        maxPosition = Math.max(maxPosition, nums[i] + i); 
        
        // 当遍历到当前边界时
        if (i == end) { 
            // 更新边界为能跳到的最远位置
            end = maxPosition;
            // 增加一步
            steps++;
        }
    }
    
    // 返回步数
    return steps;
}