题目
给定一个非负整数数组 nums。一开始位于数组的第一个位置，数组中的数字代表该位置能跳到的最大距离。
如果能到达最后一个位置，返回 true，否则返回 false。
解析
以 [2,3,1,1,4]，能达到最后一个位置，即是说，前边有一个可达的位置，其跳跃的覆盖范围包括最后一个位置。换句话说，前边所有的数，其最远覆盖范围超过 last index。
从第一个数 nums[0]=2 出发，我们发现最大覆盖范围是 。因为 0+nums[0] =2。
所以一个可达的位置，其最远覆盖范围是 i+nums[i]。在最远覆盖范围里，所有的位置都是可达的。可以从前往后遍历，一直更新最远覆盖范围，一旦最远覆盖范围大于数组的最后索引，说明可达，否则，不可达。
- 设置一个最远覆盖范围 len = 0
- 从第一个数开始，首先判断该数是否可达，即 len>=i
- 如果不可达，结束返回 false
- 如果可达且是末尾游标，返回 true，更新最大值 len = max(len, i+nums[i])
伪代码
var length int
for i:=0;i<len(nums);i++
if length < i
return false
length = max(length, i+nums[i])
return true
代码
func canJump(nums []int) bool {
var length int
for i:=0;i<len(nums);i++{
if length<i{
return false
}
if i+nums[i] > length {
length = i+nums[i]
}
if length>= len(nums)-1 {
return true
}
}
return true
}
image.png
后记
- 函数调用对刷题来说，代价挺大
- 注意边界条件，我们一直从 0 开始遍历到数组结束，设置初始 length 为 0，以使 0 也满足这个规律。先判断不可达直接返回 false，这样后边的逻辑就是可达，在可达里，我们判断是否可达最远并更新最大值。这样代码是最工整的。
- 最后的结果无论返回 true 还是 false 都无所谓，因为我们遍历完了整个数组，最后的结果总会在循环中产生。
