55. Jump Game

https://leetcode.com/problems/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: nums = [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: nums = [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.

Constraints:

• 1 <= nums.length <= 3 * 10^4

• 0 <= nums[i][j] <= 10^5

数组元素值代表从该点能最远往前蹦多远，问从0开始能否蹦完整个数组。greedy，nxt表示最远能蹦到的位置，cur表示遍历到的当前位置，当cur + nums[cur] > nxt时更新nxt。当cur超出nxt范围意味着到达蹦不到的位置，返回false。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        nxt = 0
        for cur, v in enumerate(nums):
            if cur > nxt:
                return False
            nxt = max(nxt, cur + v)
        return True