按关键词阅读：
Go 实现
func minJump(jump []int) int {if len(jump) == 0 {return 0}n := len(jump)queue := [][]int{}visited := map[int]int{}queue = append(queue, []int{0, 1})visited[0] = 1far := 1for i := 0; i < len(queue); i++ {idx, step := queue[i][0], queue[i][1]if idx + jump[idx] >= n {return step}if _, ok := visited[idx + jump[idx]]; !ok {queue = append(queue, []int{idx + jump[idx], step + 1})visited[idx + jump[idx]] = step + 1}for j := far; j < idx; j++ {if _, ok := visited[j]; !ok {queue = append(queue, []int{j, step + 1})visited[j] = step + 1}}far = Max(far, idx)}return -1} func Min(x, y int) int {if x < y {return x}return y} func Max(x, y int) int {if x > y {return x}return y}复杂度分析
时间复杂度：O(n) 。
空间复杂度：O(n) 。
方法三：线段树考虑第 i 个位置 ， 可以直接跳到 i+jump[i] ， 也可以跳两步跳到所有的 i+1 .. i+jump[i]-1 。 所以就有了递推方程：
- f[i+jump[i]] = max(f[i + jump[i]], f[i] + 1) 向右跳
- f[j] = max(f[j], f[i] + 2), i < j < i+jump[i] 向左跳
- clearT() 线段树初始化 。 编号 0 弹簧操作数为 0；其余的最小操作数为 -1 ， 表示暂不可到达
- setTree(cl,cr,val) 更新编号 cl ~ cr 之间弹簧的最小操作数为 val 。 如果内部弹簧最小操作数已经小于等于 val ， 则保持不变 ， 否则更新为 val
- getTree(curr) 获得编号 curr 弹簧的跳跃最小值
Go 实现
var g[4000001]intfunc minJump(jump []int) int {n := len(jump)res := nclearTree(0,0,n-1)for i:=0; i= n {res = min(res, curr+1)}else {setTree(0,0,n-1,i+jump[i],i+jump[i],curr+1)}if i+1<=i+jump[i]-1 {setTree(0,0,n-1,i+1,min(n-1,i+jump[i]-1),curr+2)}}return res}func setTree(index, l, r, cl, cr, val int){if g[index]!=-1if curr<=mid {res = getTree(index*2+1, l, mid, curr)}else{res = getTree(index*2+2, mid+1, r, curr)}if g[index] != -1 {if res == -1 {res = g[index]} else {res = min(g[index],res)}}return res}func clearTree(index, l, r int){g[index] = -1if l==r {if l==0{g[index] = 0}return}mid := (l+r)/2clearTree(index*2+1, l, mid)clearTree(index*2+2, mid+1,r)}func min(x, y int) int {if x < y {return x}return y} func max(x, y int) int {if x > y {return x}return y} 复杂度分析时间复杂度：O(n*log(n)) 。
空间复杂度：O(n) 。
本文作者：力扣
编辑&版式：霍霍
声明：本文归“力扣”版权所有 ， 如需转载请联系 。
稿源：(未知)
【傻大方】网址：http://www.shadafang.com/c/111J2T552020.html
标题：LeetCode 题解 | 力扣杯 LCP 09.最小跳跃次数( 二 )