leetcode45:跳跃游戏II(贪心算法)

leetcode45:跳跃游戏II

• 题目：

  • 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

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

    判断你是否能够到达最后一个下标。

• 思路：贪心算法

• 代码如下：

class Solution {
    public int jump(int[] nums) {
        int res = 0;
        //下一步覆盖最远距离
        int nextDistance = 0;
        //当前覆盖最远距离
        int curDistance = 0;
        int n = nums.length;
        //提前对当前可以走的最远距离+1
        //当当前可以走的最远距离超过nums的长度-2时，说明已经符合要求，直接返回结果即可
        for(int i = 0; i <= curDistance && curDistance < n - 1; i++){
            //从上一次走的最远最远距离开始，记录下一次走的最远距离
            nextDistance = Math.max(nextDistance,i+nums[i]);
            if(i == curDistance){
                //说明已经到达当前走最远距离，将下次走的最远距离赋值给当前走的最远距离，跳跃数+1
                curDistance = nextDistance;
                res++;
            }
        }
        return res;
    }
}