0055. 跳跃游戏【中等】
1. 📝 题目描述
给你一个非负整数数组 nums,你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true;否则,返回 false。
示例 1:
txt
输入:nums = [2, 3, 1, 1, 4]
输出:true1
2
2
解释:可以先跳 1 步,从下标 0 到达下标 1,然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
txt
输入:nums = [3, 2, 1, 0, 4]
输出:false1
2
2
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0,所以永远不可能到达最后一个下标。
提示:
1 <= nums.length <= 10^40 <= nums[i] <= 10^5
2. 🎯 s.1 - 贪心
c
bool canJump(int* nums, int numsSize) {
int maxReach = 0;
for (int i = 0; i < numsSize; i++) {
if (i > maxReach)
return false; // 当前位置不可达
int reach = i + nums[i];
if (reach > maxReach)
maxReach = reach;
if (maxReach >= numsSize - 1)
return true;
}
return true;
}1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
js
/**
* @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
}1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
py
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach = 0
for i in range(len(nums)):
if i > max_reach: return False # 当前位置不可达
max_reach = max(max_reach, i + nums[i])
if max_reach >= len(nums) - 1: return True
return True1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
- 时间复杂度:
,只需遍历一次数组 - 空间复杂度:
,只使用常数额外空间
算法思路:
- 维护
maxReach表示当前能到达的最远位置,初始为 0 - 遍历数组,若当前下标
i > maxReach,说明无法到达当前位置,返回false - 否则更新
maxReach = max(maxReach, i + nums[i]),若maxReach >= n - 1,提前返回true