We maintain a global farthest distance can be reached,
reach, and a
local farthest distance can be reached within the global
We update local everytime we go to a new position, which is indexed by
If we achieve
global position, we look at local and update
Continue until we reach the end of the list.
def jump(self, nums): """ :type nums: List[int] :rtype: int """ step, reach, local, pos = 0, 0, 0, 0 while reach < len(nums)-1: local = max(local, pos+nums[pos]) if pos == reach and local > reach: reach = local step += 1 pos += 1 return step