LeetCode 45 跳跃游戏 II

题目链接：

https://leetcode.cn/problems/jump-game-ii/

以下是使用Go语言实现外观数列问题的代码：

func jump(nums []int) int { maxpos := 0 // 最远可到达距离 last := 0 // 上一次起跳位置 step := 0 // 步数 for i := 0; i < len(nums)-1; i { // 注意循环条件，最后一个位置不需要遍历 maxpos = max(maxpos, i nums[i]) // 更新最远可到达距离 if i == last { // 当前位置已经到达上一次起跳位置，需要起跳一次 last = maxpos // 更新起跳位置为最远可到达距离 step // 步数加1 } } return step } func max(a, b int) int { if a > b { return a } return b }

执行用时：8 ms, 在所有 Go 提交中击败了96.46%的用户

内存消耗：5.8 MB, 在所有 Go 提交中击败了37.56%的用户

通过测试用例：109 / 109

题解：

这是一道经典的贪心算法题目，我们首先可以考虑贪心算法的思路来解决这个问题。我们假设当前可以到达的最远距离为maxpos，当前的步数为step，最后一次起跳的位置为last，则根据题意我们可以得出以下贪心策略：

1. 从位置0开始，遍历整个数组，每次遍历时，用maxpos更新最远可到达距离。
2. 在遍历过程中，如果当前位置i小于等于last nums[last]，则说明在跳一步的前提下，可以到达位置i，因此更新last的位置。
3. 如果本次遍历到的位置i已经到达了最远可到达距离maxpos，则需要起跳一次，步数加1，并且更新最远可到达距离。

时间复杂度分析

在上述代码中，我们只需要一次遍历整个数组，因此时间复杂度为 O(n)。

空间复杂度分析

在上述代码中，只需要使用常数个变量，因此空间复杂度为 O(1)。