大纲

判断给定数组从第一个元素开始,能否跳动到最后个位置

示例

  1. nums = [2,3,1,1,4]
  2. true
  3. 可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
  1. nums = [3,2,1,0,4]
  2. false
  3. 无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

思路

  1. 最大跳跃数如果大于等于数组长度，就代表能够跳跃，并不是一定要到数组的最后个位置
  2. 每次跳跃的时候,都是当前位置加上可跳跃的长度记录下来
  3. 每次跳跃的时候,都比较下当前位置是否超过了记录的跳跃长度,如果跳跃长度小于当前位置,代表跳到了无法到达的位置
  4. 每次记录长度的时候都要与上次跳跃记录下的长度取最长，然后再数组长度进行比较,（1）的逻辑

    解释

    ```javascript arr = [1,3,1,1,4]; // 当前的跳跃长度是0 distance = 0; // 进行第一次跳跃的时候,来到了下标0的地方,跳跃长度为1 distance = 0 + 1; // 记录下了跳跃长度为1

// 第二次跳跃时,下标1,跳跃长度为3 // 进行一次判断,当前的下标 i = 1;distance = 1; // 跳跃的距离没有超出可跳(distance)长度 if (i > distance) { // 如果超出范围,就表明不可跳到数组结束 return false; }

// 比较当前的位置提供的跳跃长度,是不是比上次记录的跳跃长度长 // distance = Math.max(1, 3 + 1) distance = Math.max(distance, arr[i] + i);

// 当前可跳到4的位置,所以当前直接就可以判定,能够跳到数组结尾 if (distance >= arr.length) { return true; }

  1. ```javascript
  2. arr = [3,2,1,0,4]
  3. distance = 0;
  5. // 进行第一次跳跃的时候,来到了下标0的地方,跳跃长度为3
  6. distance = 0 + 3; // 记录下了跳跃长度为3
  8. // 第二次跳跃时,下标1,跳跃长度为2
  9. // 进行一次判断,当前的下标 i = 1;distance = 3;
  10. // 跳跃的距离没有超出可跳(distance)长度
  11. if (i > distance) {
  12.   // 如果超出范围,就表明不可跳到数组结束
  13.     return false;
  14. }
  15. // 比较当前的位置提供的跳跃长度,是不是比上次记录的跳跃长度长
  16. // distance = Math.max(3, 1 + 2),没有变化
  17. distance = Math.max(distance, arr[i] + i);
  20. // 第三次跳跃时,下标2,跳跃长度为1
  21. // 进行一次判断,当前的下标 i = 2;distance = 3;
  22. // 跳跃的距离没有超出可跳(distance)长度
  23. if (i > distance) {
  24.   // 如果超出范围,就表明不可跳到数组结束
  25.     return false;
  26. }
  27. // 比较当前的位置提供的跳跃长度,是不是比上次记录的跳跃长度长
  28. // distance = Math.max(3, 2 + 1), 没有变化
  29. distance = Math.max(distance, arr[i] + i);
  32. // 第四次跳跃时,下标3,跳跃长度为0
  33. // 进行一次判断,当前的下标 i = 3;distance = 3;
  34. // 跳跃的距离没有超出可跳(distance)长度
  35. if (i > distance) {
  36.   // 如果超出范围,就表明不可跳到数组结束
  37.     return false;
  38. }
  39. // 比较当前的位置提供的跳跃长度,是不是比上次记录的跳跃长度长
  40. // distance = Math.max(3, 3 + 0), 没有变化
  41. if (i > distance) {
  42.   // 如果超出范围,就表明不可跳到数组结束
  43.     return false;
  44. }
  46. // 第五次跳跃时,下标4,跳跃长度为4
  47. // 进行一次判断,当前的下标 i = 4;distance = 3;
  48. // 跳跃的距离超出可跳(distance)长度
  49. // 4 > 3
  50. if (i > distance) {
  51.   // 如果超出范围,就表明不可跳到数组结束
  52.     return false;
  53. }
  54. // 结束了循环,已经跳到了不可能到达的下标位置

实现

  1. function canJump(nums) {
  2.     let distance = 0;
  3.   const len = nums.length;
  4.   for (let i = 0; i < len; i++) {
  5.       if (i > distance) {
  6.         return false;
  7.     }
  8.     distance = Math.max(distance, nums[i] + i);
  9.     if (distance >= len) {
  10.       return true;
  11.     }
  12.   }
  13.   return true;
  14. }