跳跃游戏

分析

这题保持一个思路「维护一个最大值，当最大值大于当前值时使用最大值 $- 1$ 的步数」即可硬解出来。

当然这其实有点 trick，正确的做法应该是使用贪心的思路去解答。当 max_jump 的值大于 i 时，意味着此时 i 的值可达。此时可通过比较 max_jump 和 i + nums[i] 的最大值，并将结果存储与 max 中。而当 max_jump 大于等于数组最大索引时，满足条目条件，返回真值。当 max_jump 不大于 i 时，意味着不可达。返回假值。

解答

1
class Solution {
2
public:
3
  bool canJump(vector<int> &nums) {
4
    auto max_jump = 0;
5
    auto n = nums.size();
6

7
    if (n == 1)
8
      return count;
9

10
    for (auto i = 0; i < n; ++i) {
11
      if (i <= max_jump) {
12
        max_jump = max(max_jump, i + nums[i]);
13

14
        if (max_jump >= n - 1)
15
          return true;
16
      } else
17
        break;
18
    }
19

20
    return false;
21
  }
22
};