题干:
给定一个长度为 n
的 0 索引整数数组 nums
。初始位置为 nums[0]
。
每个元素 nums[i]
表示从索引 i
向前跳转的最大长度。换句话说,如果你在 nums[i]
处,你可以跳转到任意 nums[i + j]
处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1]
的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]
。
跳跃游戏1是55.跳跃游戏,可以点链接对照看看:55题是问是否能跳到最后;45题是跳到最后的步数最少是多少,都是贪心算法
解法:贪心算法
func jump(nums []int) int {
n := len(nums)
if n <= 1 {
return 0
}
jumps := 0 // 跳跃次数
currentEnd := 0 // 当前跳跃的结束位置
farthest := 0 // 下一跳的最远位置
for i := 0; i < n-1; i++ {
// 更新下一跳的最远位置
farthest = max(farthest, i+nums[i])
// 如果到达当前跳跃的结束位置,增加跳跃次数
if i == currentEnd {
jumps++
currentEnd = farthest // 更新当前跳跃的结束位置
}
}
return jumps
}
// 辅助函数,返回两个整数中的较大值
func max(a, b int) int {
if a > b {
return a
}
return b
}
解析:
贪心策略
-
跳跃范围:
- 在每一步中,我们需要确定从当前位置可以跳到的最远位置。这个最远位置是通过当前索引
i
和nums[i]
计算得出的,即farthest = max(farthest, i + nums[i])
。 farthest
变量记录了在当前跳跃范围内(从currentEnd
到farthest
)可以到达的最远位置。
- 在每一步中,我们需要确定从当前位置可以跳到的最远位置。这个最远位置是通过当前索引
-
跳跃计数:
- 当我们遍历到当前跳跃的结束位置
currentEnd
时,意味着我们需要进行一次跳跃来继续前进。此时,我们增加跳跃次数jumps
,并将currentEnd
更新为farthest
,以便在下一次跳跃中使用。 - 这意味着我们在每次到达当前跳跃范围的末尾时,都会进行一次跳跃,并更新我们的跳跃范围。
- 当我们遍历到当前跳跃的结束位置
-
终止条件:
- 当我们遍历到倒数第二个元素(
n-1
),我们不需要再进行跳跃,因为我们已经可以到达最后一个元素。
- 当我们遍历到倒数第二个元素(
具体示例:
考虑数组 nums = [2, 3, 1, 1, 4]
:
- 从索引
0
开始,nums[0] = 2
,我们可以跳到索引1
或2
。此时farthest = 2
。 - 当我们到达索引
1
,nums[1] = 3
,我们可以跳到索引2
、3
或4
。此时farthest = 4
。 - 由于我们已经到达了当前跳跃的结束位置(
currentEnd = 2
),我们增加跳跃次数,更新currentEnd
为farthest
(即4
)。 - 继续遍历,发现我们已经可以到达最后一个元素,因此跳跃次数为
2
。
复杂度分析:
时间复杂度:
- 该算法的时间复杂度为 O(n),其中 n 是数组的长度,因为我们只遍历了一次数组。
空间复杂度:
- 空间复杂度为 O(1),只使用了常数级别的额外空间。