[LeetCode45题 – 跳跃游戏II] | 刷题打卡

掘金团队号上线，助你 Offer 临门！ 点击 查看详情

前言

昨天做了 跳跃游戏 ，主要分享了 贪心算法 的解题思路，今天一起来接着跳吧。仍然是一个贪心算法题，思路大概如初一辙，话不多说，直接上题目吧。

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
复制代码
复制代码

说明: 假设你总是可以到达数组的最后一个位置。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/im…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

这题与昨天的 跳跃游戏 的区别就在于，昨天需要我们去判断是否能够跳到最后一个坐标，而这个默认是可以到达最后的坐标的。接下来简单分析一下这一题的解题思路。

仍然是采用贪心算法，每次在可跳范围内选择可以跳的更远的位置。如图，实线表示当前坐标的可跳范围，虚线表示可跳范围的坐标可以跳跃的最远距离。对于当前坐标，可跳范围是 2 和 3 。但是因为 3 可以跳到更远的 2 的位置。而 2 只能跳到 1 的位置，所以跳到 3 上面。

跳到 3 的位置上之后，可跳范围为 1 5 2，显然 5 可以跳到最远的距离，因此跳到 5 上面。最小步数就是 2 。

如果我们定义一个变量 maxLength 维护当前跳到的最大距离. 并且定义一个变量 border 表示当前可跳范围的边界值。因为这题始终都是可以跳到最后的。也就是当遍历完当前的可跳范围。新的可跳范围就是当前 border 到 maxLength ，这时候说明已经跳过，所以增加一次步数。我们把 maxLength 赋给 border 。重复这个逻辑，那么一直到最后一次 border 肯定是大于等于数组长度的。

最终代码

class Solution {
    
    public int jump(int[] nums) {
        int border = 0;
        int maxLength = 0; 
        int steps = 0;
        for(int i = 0; i < nums.length - 1; i++){
            maxLength = Math.max(nums[i] + i,maxLength); 
            if( i == border){ 
                border = maxLength;
                steps++;
            }
        }
        return steps;
    }
}
复制代码
复制代码

结语

本题是一个典型的 贪心算法 典型的贪心算法，通过局部最优解得到全局最优解，解法的时间复杂度为 O(n) 。但是本题需要注意一个细节，因为 因为第一次不管怎么跳都要保证计数一次，因此当 i==0 时,我们令 border 为 0 。这样第一次无论如何都会计数一次，第二点就是当跳到 num[] 最后一个元素是时候其实已经是结束了的。如果我们循环条件采用 i < nums.length ，如果存在跳到最后一个元素之后，其实还是满足当前元素的。此时 i == border 仍会计数一次。因此需要控制好循环条件。

本文正在参与「掘金 2021 4 月刷题打卡」, 点击查看 活动详情。喜欢的话点个赞吧。