一、题目内容 简单中等困难

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

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

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

假设你总是可以到达数组的最后一个位置。

示例1：

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

示例2：

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

二、解题思路

首先题目给了前提条件，跳跃肯定能够跳到最后一格的，所以我们不用考虑跳不到的情况。
只需要考虑怎么用 最少的步数 跳到 最后一格。这里关键的问题在于，何时给步数加 1。

初始步数 count = 0，结束的格子位置 end
每个格子的位置index，在这个格子能跳跃的格子数为step，故能覆盖的范围为cover = index + step
我们用示例 1 来推演一下。

[2, 3, 1, 1, 4] 每个格子对应的 step，一格一格走 |———>| |—————>| 两步能到达终点。 当走到第一个覆盖范围，且覆盖范围不能达到尽头 end 时， 步数 count + 1 当走到第二个覆盖范围，且覆盖范围直接达到尽头 end 时，步数 count + 1，此时 cover >= end，直接结束。

另一个示例

[3, 1, 2, 1, 4]每个格子对应的 step，一格一格走 |—————>| |—>| |———->| 当走到第一个覆盖范围，且覆盖范围不能达到尽头 end 时候， 步数 count + 1 当走到第二个覆盖范围，但没超出第一个覆盖范围，且没达到尽头 end 时，步数 count 不变 当走到第三个覆盖范围，但能直接达到尽头 end 时，步数 count + 1，此时 cover >= end，直接结束。

所以 步数加 1 的条件就是

  1. 当这次覆盖范围不能达到尽头 end 时，
    1. 如果走到的位置没有超出上一次覆盖范围，则不改变步数
    2. 如果走到的位置超出上一次覆盖范围，则步数 + 1
  2. 当这次覆盖范围能达到尽头 end 时，步数 + 1，结束程序，返回步数

那什么时候更新 cover 呢，我们需要记录之前走过最长的 cover，记为 nextCover
走每一格的时候，记录下最长的 nextCover
当走到的位置 index，达到当前 cover 的尽头时，更新 cover

再来个示例 [1, 2, 2, 1, 4]每个格子对应的 step，一格一格走 |—>| |———>| |———->| 当走到第一个覆盖范围，且覆盖范围不能达到尽头 end 时候， 步数 count + 1 当走到第二个覆盖范围，超出第一个覆盖范围，且没达到尽头 end 时，步数 count + 1 当走到第三个覆盖范围，但能直接达到尽头 end 时，步数 count + 1，此时 cover >= end，直接结束。

三、具体代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var jump = function (nums) {
  6.   const end = nums.length;
  7.   // 如果只有一格，根本不用跳
  8.   if (end === 1) return 0;
  9.   // 初始化
  10.   let count = 0, curCover = nums[0], nextCover = 0;
  11.   // 开始遍历
  12.   for (let i = 0; i < end; i++) {
  13.     // 每一格都记录下一次能覆盖的最大范围
  14.     nextCover = Math.max(nextCover, i + nums[i]);
  15.     // 如果当前覆盖范围能达到终点 end
  16.     if (curCover >= end) {
  17.       count++;
  18.       break;
  19.     } else {
  20.       // 如果当前覆盖范围不能达到终点 end
  21.       // 当走到当前覆盖范围的最后一格时，进行处理
  22.       if (i === curCover) {
  23.         curCover = nextCover;
  24.         count++
  25.       }
  26.     }
  27.   }
  28.   return count;
  29. };
  30. /**
  31.  * 时间复杂度：O(n)
  32.  * 空间复杂度：O(1)
  33.  */

四、其他解法

下面方法的不同之处在于，end = nums.lengt - 1，而不是end = nums.length。
这样做，只要它最多能覆盖到倒数第二格时，再走一格（count++）就是终点
如果它能覆盖到最后一格，那么 i ，必定 i < curCover，也就是不需要再走一格，省去了许多判断的麻烦

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var jump = function (nums) {
  6.   const end = nums.length - 1;
  7.   let count = 0, curCover = 0, nextCover = 0;
  8.   for (let i = 0; i < end; i++) {
  9.     nextCover = Math.max(nextCover, i + nums[i]);
  10.     if (i === curCover) {
  11.       curCover = nextCover;
  12.       count++;
  13.     }
  14.   }
  15.   return count;
  16. };
  17. /**
  18.  * 时间复杂度：O(n)
  19.  * 空间复杂度：O(1)
  20.  */