【貪心】LeetCode 55. 跳躍遊戲【中等】

給定一個非負整數數組 ​

​nums​

​ ，你最初位于數組的 第一個下标 。

數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最後一個下标。

示例 1：

輸入：nums = [2,3,1,1,4]

輸出：true

解釋：可以先跳 1 步，從下标 0 到達下标 1, 然後再從下标 1 跳 3 步到達最後一個下标。

示例 2：

輸入：nums = [3,2,1,0,4]

輸出：false

解釋：無論怎樣，總會到達下标為 3 的位置。但該下标的最大跳躍長度是 0 ， 是以永遠不可能到達最後一個下标。

提示：

1 <= nums.length <= 3 * 104

0 <= nums[i] <= 105

【分析】

貪心思路解決。

class Solution:
    def canJump(self, nums) :
        max_i = 0       #初始化目前能到達最遠的位置
        for i, jump_step in enumerate(nums):   #i為目前位置，jump_step是目前位置的跳數
            if max_i >= i and i + jump_step > max_i:  #如果目前位置能到達，并且目前位置+跳數>最遠位置  
                max_i = i+jump_step  #更新最遠能到達位置
        return max_i >= i      

# 另外，将end_index存下來，然後每次更新max distance時，都去對比一下，能不能到達末尾。不用完全周遊完，再去确定能不能到達末尾。
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if nums == [0]: return True
        maxDist = 0
        end_index = len(nums)-1
        for i, jump in enumerate(nums):
            if maxDist >= i and i+jump >= maxDist:
                maxDist = i+jump
                # 增加這一判斷
                if maxDist >= end_index:
                    return True
        
        return False