045._Jump_Game_II.md

45. Jump Game II

题目: https://leetcode.com/problems/jump-game-ii/

难度:

Easy

思路

greedy solution, the current jump is [i, cur_end], and the cur_farthest is the farthest point that all of point in [i, cur_end] can reach, whenever cur_farthest is larger than the last point' index, return current jump+1; whenever i reaches cur_end, update cur_end to current cur_farthest.

• Time: O(log(n))
• Space: O(1)

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # Note You can assume that you can always reach the last index.
        cur_end, cur_farthest, step, n = 0, 0, 0, len(nums)
        for i in range(n-1):
            cur_farthest = max(cur_farthest, i + nums[i])
            if cur_farthest >= n - 1:
                step += 1
                break
            if i == cur_end:
                cur_end = cur_farthest
                step += 1
        return step