55. Jump Game

问题

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

例子

A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

分析

维护一个能跳到的最远范围，如果这个范围覆盖到了最后一个节点，则说明可以从第一个节点跳到最后一个节点。

要点

如果数组的元素表示的是只能跳的步数，那么可以用bfs来解决。

时间复杂度

O(n)

空间复杂度

O(1)

代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int reach = 0; // 能跳到的最远范围
        for (int i = 0; i < nums.size() && i <= reach; i++) { // 当i在范围之外时，说明已经跳不到i了
            reach = max(reach, i + nums[i]); // 更新最远范围
        }
        return reach >= nums.size() - 1;
    }
};