Jump Game

题目分析：找出能够到达的最远距离是否能到最后一个索引。
我的想法是从第一个开始，不断更新最长到达位置，直到最长位置超过最后一个索引。

代码

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

时间O（n），空间O（1）

满分答案

通过最后一个向前寻找，不断更新最末端位置，如果能够遍历到0，则说明可以到达。

public class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

时间O（n），空间O（1）。