LeetCode 55 跳跃游戏

题目链接：

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

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

func canJump(nums []int) bool { maxJump := 0 // 当前位置能够跳到的最远位置 for i := 0; i < len(nums); i { if i > maxJump { // 当前位置已经无法到达 return false } maxJump = max(maxJump, i nums[i]) // 更新当前位置能够跳到的最远位置 if maxJump >= len(nums)-1 { // 已经可以到达最后一个位置 return true } } return true } func max(a, b int) int { if a > b { return a } return b }

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

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

通过测试用例：171 / 171

该算法使用贪心思想，从左往右遍历数组，用变量maxJump记录当前位置能够跳到的最远位置。在遍历的过程中，如果当前位置已经无法到达，即当前位置大于maxJump，则返回false。如果maxJump已经能够到达最后一个位置，则返回true。最后，如果能够成功遍历完整个数组，则返回true。

该算法的时间复杂度为O(n)，其中n为数组的长度，因为只需要遍历一次数组即可得出结果。空间复杂度为O(1)，因为只需要使用常数个变量来存储中间结果。

在代码实现中，使用了一个max函数来返回两个整数的较大值，这是因为Go语言没有内置的max函数。

对于每一个位置i，可以跳跃的最大长度为nums[i]，因此从当前位置可以到达的最远位置为i nums[i]。因此，我们可以用一个变量maxJump来记录当前位置能够跳到的最远位置。在遍历数组时，如果当前位置i大于maxJump，则说明当前位置已经无法到达最后一个位置，因此返回false。如果maxJump已经大于等于最后一个位置，则说明可以到达最后一个位置，返回true。最后，如果能够成功遍历完整个数组，则说明可以到达最后一个位置，返回true。