LeetCode-Jump Game II

这道题的策略是每次都要找到当前能跳到的最远的情况。

这里参考了 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
}