跳跃游戏

贪心

说明

持续更新当前能到达的最远位置；若当前位置超过最远边界则不可达。

分析

遍历到位置 i 时，reach 表示先前位置能到达的最远边界。若 i 已超过 reach，则任何更后位置都不可能由此前路径到达；否则用 i+a[i] 扩大边界。

图解推演

对 [2,3,1,1,4]，从下标 0 可达边界 2；扫描到可达的下标 1 后，将边界扩为 4，因此末尾可达。边界是可达区间的摘要，不代表每次实际都跳到该位置；若在 [3,2,1,0,4] 的下标 4 才试图更新，就已经越过边界 3，必须先判失败。

查看图表代码

适用前提与边界

这个贪心只判断能否到达，不计算最少跳跃次数。

示例输入与调用

fmt.Println(CanJump([]int{2, 3, 1, 1, 4}))

运行输出

true

完整 Go 示例

package main

import "fmt"

func CanJump(a []int) bool {
	reach := 0
	for i, step := range a {
		if i > reach {
			return false
		}
		if i+step > reach {
			reach = i + step
		}
	}
	return true
}

func main() {
	fmt.Println(CanJump([]int{2, 3, 1, 1, 4}))
}