原链接：https://leetcode-cn.com/leetbook/read/leetcamp-2/aag0zh/

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

    示例一：

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

    示例二：

    输入: nums = [2,3,0,1,4] 输出: 2

    题解一：优化后的贪心算法

    • 不断维护可达区间的右端点r

    image.png
    image.png
    image.png

    • 遍历每个位置，对于每个位置 i 确定是几步可达：假设第 i 个位置可跳跃长度为 ai，则区间 [i+1,i+ai] 均为 x+1 步可达，其中 x 为步数，下面的r是右端点。
      • r<i+ai：区间 [r+1,i+ai] 为之前不可达，且现在可达的点。由于点 i 为能够到达该位置的第一个点，所以到达次新区间的最小步数为 x+1，将其记录于步数数组中。
      • r>=i+ai：不会有新区间产生
        1. /**
        2. * @param {number[]} nums
        3. * @return {number}
        4. */
        5. var jump = function(nums) {
        6. const steps = [0];
        7. let r = 0;
        8. for(let i = 0;i<nums.length;i++){
        9.    let nr = i + nums[i];
        10.    if(nr < r){
        11.        continue;
        12.    }else{
        13.        for(let j=r+1;j<nr+1;j++){
        14.            steps.push(steps[i]+1);
        15.        }
        16.        r = nr;
        17.    }
        18. }
        19. return steps[nums.length - 1];
        20. };