45. 跳跃游戏 II（高频题）

45. 跳跃游戏 II

• 题目
• 解题思路
• 代码

题目

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

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

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

解题思路

见书379

代码

class Solution {
    public int jump(int[] nums) {
        int n=nums.length;
        //站在索引i最多能挑到索引end
        int end=0;
        //从索引[i...end]起跳，能到达的最远距离
        int farthest=0;
        //记录跳跃的次数
        int jumps=0;
        for(int i=0;i<n-1;i++){
            farthest=Math.max(nums[i]+i,farthest);
            if(end==i){//即当前这个区间走完
            //如果还是不能理解就看书P.380的那幅图
                jumps++;//那就要跳第二步了。
                end=farthest;
            }
        }
        return jumps;
    }
}