【Leetcode 热题 100】55. 跳跃游戏
问题背景
给你一个非负整数数组
n
u
m
s
nums
nums，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回
t
r
u
e
true
true；否则，返回
f
a
l
s
e
false
false。
数据约束
●
1
≤
n
u
m
s
.
l
e
n
g
t
h
≤
1
0
4
1 \le nums.length \le 10 ^ 4
1≤nums.length≤104
●
0
≤
n
u
m
s
[
i
]
≤
1
0
5
0 \le nums[i] \le 10 ^ 5
0≤nums[i]≤105
解题过程
由于数组中记录的是最大的跳跃长度，所以实际上只要判断最终能不能达到或者超过数组中的最后一个位置即可。
具体的做法时遍历数组的同时始终维护可达的最远位置，潘顿这个最远位置能否达到或者超过数组中的最后一个位置。
具体实现
class Solution {
public boolean canJump(int[] nums) {
int max = 0;
// 这里由于 max 增长比 i 要快，这样写能够一定程度上减少循环的次数
for(int i = 0; max < nums.length - 1; i++) {
if(i > max) {
return false;
}
max = Math.max(max, i + nums[i]);
}
return true;
}
}