45.跳跃游戏II

思路

没啥思路就直接看解析了。
有两种方法，分析如下：
贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。
ps：注意题目保证了一定可以到达终点。

方法1

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。【这里有一点抽象的思维，不管你跳的细节，能跳到就可以。】
当移动下标达到了当前覆盖的最远距离下标时

• 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。

• 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

  // 版本一
  class Solution {
  public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆盖最远距离下标
            if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                if (curDistance != nums.size() - 1) {       // 如果当前覆盖最远距离下标不是终点
                    ans++;                                  // 需要走下一步
                    curDistance = nextDistance;             // 更新当前覆盖最远距离下标（相当于加油了）
                    if (nextDistance >= nums.size() - 1) break; // 下一步的覆盖范围已经可以达到终点，结束循环
                } else break;                               // 当前覆盖最远距离下标是集合终点，不用做ans++操作了，直接结束
            }
        }
        return ans;
    }
  };

  方法二（简洁）

  针对于方法一的特殊情况，可以统一处理，即：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。
  想要达到这样的效果，只要让移动下标，最大只能移动到nums.size - 2的地方就可以了。
  难点就在于这个i的边界条件
  也可以这么理解：
  ```javascript var jump = function(nums) { if(nums.length ===1) return 0; let curDis =0; let nextDis =0; let step =0;

  //重点是这里的i的范围 for(let i =0;i<nums.length-1;i++){

    nextDis =Math.max(nums[i]+i,nextDis); //更新下一步最远可覆盖的距离
    //如果i已经走到了当前可覆盖的最远距离
    if(i===curDis){
        step++;
        curDis =nextDis;
    }

  } return step

}; ```