45. Jump Game II

LeetCode 45. Jump Game II

Description

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

• 1 <= nums.length <= 1000

• 0 <= nums[i] <= 105

Tags

Array, Greedy

Solution

以图示为例，从下标0出发，先找出它能达到的所有位置（下标1和2），再看这些位置里谁能走得最远，这里是下标1可以跳得更远，因此进入下标1。再从下标1出发，它可以达到下标2、3、4的位置，再通过比较得知如果走下标4的话可以跳得最远，选择下标4。

Take the figure above as example, starting from the 0th, we first find all positions can be reached from the starting point (1st and 2nd in this case). Then, we check which of them can go further. In terms of the both, the 1st where is "3" can jump further. Thus we choose to jump to the 1st as the first time jump. In the next round, starting from the 1st, we can reach 2nd, 3rd and 4th. By comparison, we know that if we jump into the 4th, we will jump the farthest. Thus, we choose 4th to jump into.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$

Code

func jump(nums []int) int {
	var ans, pivot, maxFar int
	for i := 0; i < len(nums)-1 && pivot < len(nums)-1; i++ {
		if i+nums[i] > maxFar { // the farthest index can be reached from i
			maxFar = i + nums[i]
		}
		if i == pivot {  // reach the right boundary of last jump range
			pivot = maxFar // start point of the next round of jump
			ans++          // enter the `ans`th step
		}
	}
	return ans
}

Reference

1. 跳跃游戏 II