1 题目

55-跳跃游戏

2 思路

倒着遍历数组，如果倒数第二个元素大于等于1,则说明只要判断能否到达倒数第二个位置即可，在此时递归，如果倒数第二个元素小于1,则继续遍历倒数第三个元素，和2比较，依次遍历即可。这个思路的时间复杂度：O(n!)，空间复杂度：O(1)。

3 题解

class Solution {
 public:
  bool jump(vector<int>& nums, int n) {
    if (n <= 1) return true;
    if (n == 2) return nums[0] >= 1;

    for (int i = n - 2, j = 1; i >= 0; --i, ++j) {
      if (nums[i] >= j) {
        if (jump(nums, i + 1)) return true;
      }
    }

    return false;
  }

  bool canJump(vector<int>& nums) { return jump(nums, nums.size()); }
};

提交能过一半测试用例，报错显示超时。

4 官方题解学习

贪心。遍历一遍数组，维护能访问的最远下标 rightmost。

时间复杂度：O(n)，空间复杂度：O(1)。

class Solution {
 public:
  bool canJump(vector<int>& nums) {
    int n = nums.size();
    int rightmost = 0;
    for (int i = 0; i < n; ++i) {
      if (i <= rightmost) {
        rightmost = max(rightmost, i + nums[i]);
        if (rightmost >= n - 1) return true;
      } else
        break;
    }
    return false;
  }
};