跳跃游戏
🟡 中等题目描述
给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
示例 1
输入：nums = [2, 3, 1, 1, 4]
输出：true
解释：可以先跳 1 步到下标 1，然后跳 3 步到最后一个下标示例 2
输入：nums = [3, 2, 1, 0, 4]
输出：false
解释：无论怎样，总会到达下标 3，但该位置的最大跳跃长度为 0，所以永远不能到达最后一个下标提示
1 <= nums.length <= 10^40 <= nums[i] <= 10^5
解法
参考答案 (2 个标签)
贪心 O(n)
思路
维护一个变量 maxReach 表示当前能到达的最远位置。遍历数组，如果当前位置超过 maxReach，说明无法到达；否则更新 maxReach。
代码实现
/**
* @param {number[]} nums
* @return {boolean}
*/
function canJump(nums) {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
图解
nums = [2, 3, 1, 1, 4]
i=0: maxReach = max(0, 0+2) = 2
i=1: maxReach = max(2, 1+3) = 4
i=2: maxReach = max(4, 2+1) = 4
i=3: maxReach = max(4, 3+1) = 4
i=4: maxReach = max(4, 4+4) = 8
遍历完成，返回 true