45. 跳跃游戏 II

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

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

解法

时间复杂度：O(n)
空间复杂度：O(1)
贪心法，遍历列表，用reachable来表示当前可到达的最远下标，当下标==reachable的时候，说明不能往下走了，需要增加一次跳跃；
遍历的时候用max来表示，当前可以达到的最远下标；

class Solution {
    public int jump(int[] nums) {
        
        int reachable = 0;  //目前可到达的下标
        int count = 0;  //跳跃的步数
        int max = 0;    //遍历过程可到达的最大下标
        
        for(int i=0; i<nums.length - 1; i++){
            max = Math.max(max,i + nums[i]);    //遍历保存最大的可到达下标
            if(i == reachable){    //表示到了本次跳跃的最大距离，需要进行下一次跳跃
                reachable = max;   //更新可到达的最大下标；
                count++;    
            }
        }

        return count;
    }
}