【面试经典150题】跳跃游戏Ⅱ

题目链接

给定一个长度为 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]。

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

这题借鉴了跳跃游戏的第一个解法的思路。

也就是找出并跳到[i,i+nums[i]]范围里索引+值最大的一个。

你每一步可以跳得更远才能更快得到达目的地。这就是每一步最优的贪心算法。

/*** @param {number[]} nums* @return {number}*/
var jump = function(nums) {if(nums.length===1){return 0;}let i = 0;let nextIndex;let maxVal = 0;let minStep=0;while (i + nums[i] < nums.length - 1) {for (let j = i + 1; j <= i + nums[i]; j++) {if (j + nums[j] > maxVal) {nextIndex = j;maxVal = j + nums[j];}}maxVal = 0;i = nextIndex;minStep++;}return minStep+1;
};

时间复杂度：$O(n\ast Max(nums[i]))$

空间复杂度：$O(1)$

上面的方法是主动寻找j+nums[j]最大值，我们可以维护一个最大可达位置maxReach来被动的求出最大值。

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

为什么是nums.length-1？

该算法阐述了一个过程：每次达到上一次跳跃的位置的可跳跃边界时，step++提前跳跃，跳到这一阶段的maxReach对应的位置，当然我们不需要知道这个位置，而i达到nums.length-1时，就不要再跳了，因为每次到达边界时我们就提前跳了，就不会漏一次。