题目描述

题目链接

https://leetcode.cn/problems/jump-game-ii/

思路

这道题是典型的贪心算法，通过局部最优解得到全局最优解。我们可以「贪心」地进行正向查找，每次找到可到达的最远位置，这样就可以在线性时间内得到最少的跳跃次数。

例如，对于数组，初始位置是下标，从下标出发，最远可到达下标。下标可到达的位置中，下标的值是，从下标出发可以达到更远的位置，因此第一步到达下标。从下标出发，最远可到达下标。下标可到达的位置中，下标的值是，从下标出发可以达到更远的位置，因此第二步到达下标。

在具体的实现中，我们维护当前能够到达的最大下标位置。我们从左到右遍历数组，在遍历过程中，记录在当前范围内下一次跳跃能够跳到的最远位置，当遍历到时，需要更新并将跳跃次数增加。注意，在遍历数组时，我们不访问最后一个元素，因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。但如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

还是以上图为例，当从下标开始跳跃时，我们最远可到达下标处，此时。我们从左到右遍历数组，在下标处，我们下一次能跳的最远位置，而在下标处，我们下一次能跳的最远位置，我们「贪心」地选择可到达的最远位置，即，因此跳到下标的位置。以此类推……

代码实现

public int jump(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }
    // 当前能够到达的最大下标位置
    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;
}

复杂度分析

• 时间复杂度：，其中是数组长度。
• 空间复杂度：。