跳跃游戏 II。给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。
准备三个变量，step，cur，next。step是步数，cur是当前可达，next是下次可达。遍历数组，当cur小于i，步数加1，下次可达变成当前可达，下次可达取自己和i+arr[i]的最大值。最后返回step。时间复杂度是O(N)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
ret := jump(arr)
fmt.Println(ret)
}
func jump(arr []int) int {
if len(arr) == 0 {
return 0
}
step := 0
cur := 0
next := 0
for i := 0; i < len(arr); i++ {
if cur < i {
step++
cur = next
}
next = getMax(next, i+arr[i])
}
return step
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
