045 Jump Game II
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
