55. Jump Game.md

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.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

Solution

和上一个jump game类似，增加一个判断，如果当前last_max_dist已经可以到达最后一个index的话，就返回True。

返回False的原因是还未抵达最后的index，并且无法再往前了。(last_max_dist == cur_max_dist)。

Code

class Solution:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums)<=1:
            return True
        
        last_max_dist = 0
        cur_max_dist = 0
        for i, c in enumerate(nums):
            cur_max_dist = max(cur_max_dist, i + c)
            if cur_max_dist >= len(nums)-1:
                return True
            if i == last_max_dist:
                if last_max_dist == cur_max_dist:
                    return False
                last_max_dist = cur_max_dist
        return True