45.跳跃游戏Ⅱ

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

  • 0 <= j <= nums[i] 且
  • i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

思路

  • 走到当前位置，记录下当前位置能到达的最大距离
  • 边界值end，如果当前位置等于end，则更新最大距离
  • 总次数++，表示已到达上一个位置能到的最大距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Sulution{
    public int jump(int[] nums){
        int maxPos=0;
        int end=0;
        int ans=0;
        for(int i=0;i<nums.length;i++){
            maxPos=Math.max(maxPos,nums[i]+i);
            if(i==end){
                end=maxPos;
                and++;
            }
        }
        return ans;
    }
}