LeetCode Q045Jump Game II (hard)

Q045Jump Game II (hard)



    We have to reach the last index with minimum jumps, so we should jump at the step with the largest number if possible.


    Let's take [2,3,1,5,4] as example
             [2,3,1,1,4]
 index    0 1 2 3 4

 var countJump = 0
 var maxReach = 0
 var prevReach = 0

 1. we have to jump at the nums[0]: 2, the maximum index we can reach is 2, maxReach = 2
 2. check index = 1, this is the place we have to jump
    if index > prevReach, we increase：countJump = 1,
    every time we jump update the prevReach = maxReach = 2
    maxReach = 1 + 3 = 4
 3. check index = 2, maxReach = max(maxReach, 2+1) = 4
 4. check index = 3, greater than prevReach, means this is the place we only can reach by jump, so just like step 2
    countJump = 2, prevReach = 4
    maxReach = max(4, 4) = 4
 5. check index = 4, <= maxReach
    maxReach = max(4, 4+4) = 8
 6. loop ends

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/Greedy/Q045JumpGameII.playground/Contents.swift