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

题目链接

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

• 1 <= nums.length <= $10^4$
• 0 <= nums[i] <= $10^5$

分析：

假设当前位于nums[i]，表示该元素后面的nums[i]个元素任我跳，那该跳哪个呢？

是不是得考虑跳到哪一个位置下下一步可以跳得更远。这个由index+nums[i]决定。

也就是说后面的nums[i]个元素里，哪个索引+元素值最大就跳到哪里。

/*** @param {number[]} nums* @return {boolean}*/
var canJump = function (nums) {let i = 0;let nextIndex;let maxVal = 0;while (i + nums[i] < nums.length - 1) {if (nums[i] === 0) {return false;}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;}return true;
};

时间复杂度：$O(n^2)$

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

时间复杂度太高，换个思路：

维护一个最大可达位置maxReach。

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

时间复杂度：$O(n)$

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