题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
0 <= j <= nums[i] 且
i + j < n
返回到达 n – 1 的最小跳跃次数。测试用例保证可以到达 n – 1。

示例：
输入: nums = [2,3,1,1,4]
输出: 2

题目分析

记录当前步数可跳跃的最大边界 right。
每次向右移动一位，过程中维护下一次跳跃的最大边界 nextRight。
当 index > right 时，说明进入了下一步，count++；

时间复杂度 O(n).

Java

public int jump(int[] nums) {
    int count = 0;
    int right = 0;
    int nextRight = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > right) {
            count++;
            right = nextRight;
        }
        nextRight = Math.max(nextRight, i + nums[i]);
    }
    return count;
}

Kotlin

fun jump(nums: IntArray): Int {
    var count = 0
    var right = 0
    var nextRight = 0
    for (i in nums.indices) {
        if (i > right) {
            count++
            right = nextRight
        }
        nextRight = max(nextRight, nums[i] + i)
    }
    return count
}