这道题的策略是每次都要找到当前能跳到的最远的情况。
这里参考了 Discuss 中的一个方法 ,写出了如下算法。算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
代码中设置了一个 curFastest 变量，用于指示当前位置所能跳到的最远的情况。如果到了最远的那个地方，就需要向前进一步，继续寻找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| func jump(nums []int) int {
step:=0
curEnd:=0
curFastest:=0
for i:=0;i<len(nums)-1;i++ {
if t:=i+nums[i];t>curFastest {
curFastest=t
}
if i==curEnd {
step++
curEnd=curFastest
}
}
return step
}
|