【LeetCode】0045 跳跃游戏

https://leetcode-cn.com/problems/jump-game-ii/

# -*- coding:utf-8 -*-
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        step = 0
        end = 0
        max_bound = 0
        for i in range(len(nums) - 1):
            max_bound = max(max_bound, nums[i] + i)
            if (i == end):
                step += 1
                end = max_bound
        return step
if __name__ == '__main__':
    nums = [2, 3, 1, 1, 4]
    nums = [3, 2, 1]
    # nums = [1, 1, 1, 1]
    print(Solution().jump(nums))

贪心解决，找到目前能跳到最远的距离。比如[1,1,1,1] 在idx=1的时候，最远能跳到2（1+1），因此end=max=2，当idx=2时，最远能跳到3（1+2）因此end =max =3。

比如[2,3,1,1,4]，idx0时，end =max =2，idx1时，max=end=1+3=4，idx2时，1+2<max=end，因此不更新，当idx3时，1+3=4,更新。因此我们找出了三次更新，idx分别为0 1 3.也就是三次跳转的地方。