[LeetCode] 45. Jump Game II

Given an array of non-negative integers, 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.

Example:
Input: [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.

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

跳跃游戏 II。

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题意跟版本一很接近，唯一不同的是版本一是问是否能到达终点；版本二问的是跳到最后一个位置最少需要几步（题目给的 testcase 一定能到达终点）。

思路也是贪心，但是这个题跟一般的贪心略有不同。我参考了这个帖子。因为这里求的不是每一次最远能跳几步，而是每次在可跳范围内选择可以使得跳的更远的位置。

注意代码中 for 循环停下的位置，在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
	public int jump(int[] nums) {
		int n = nums.length;
		int jump = 0;
		// 目前能到达的最远位置
		int curEnd = 0;
		// 下一次能到达的最远位置
		int nextEnd = 0;
		for (int i = 0; i < n - 1; i++) {
			nextEnd = Math.max(nextEnd, i + nums[i]);
			if (i == curEnd) {
				jump++;
				curEnd = nextEnd;
			}
		}
		return jump;
	}
}

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
	let end = 0;
	let maxPosition = 0;
	let steps = 0;
	for (let i = 0; i < nums.length - 1; i++) {
		maxPosition = Math.max(maxPosition, nums[i] + i);
		if (i === end) {
			end = maxPosition;
			steps++;
		}
	}
	return steps;
};