55. 跳跃游戏

题目描述

给定一个非负整数数组 nums，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4]
输出: true
解释: 从位置 0 跳到位置 1（跳 2 步），然后跳到位置 3（跳 3 步）, 位置 3 是最后一个位置

示例 2:

输入: nums = [3,2,1,0,4]
输出: false
解释: 从位置 0 跳到位置 1（跳 3 步），但是你还无法到达位置 3 ，因为你的最大跳跃长度为 2

题解

这个问题可以通过使用贪心算法来解决。我们可以从左到右遍历数组，同时维护两个变量：当前能够到达的最远位置 maxPosition 和当前位置 currentPosition。在每一步，我们都会更新 maxPosition 为 max(maxPosition, currentPosition + nums[i])，其中 i 是当前遍历到的索引。如果 currentPosition 达到了 maxPosition，那么我们就知道我们可以继续前进，否则我们就无法到达数组的末尾。

下面是使用 Go 语言实现的代码：

package main

import "fmt"

func canJump(nums []int) bool {
    maxPosition := 0 // 能到达的最远位置
    for i, num := range nums {
        if i > maxPosition { // 如果当前位置超出了能到达的最远位置，返回 false
            return false
        }
        maxPosition = max(maxPosition, i+num) // 更新能到达的最远位置
    }
    return maxPosition >= len(nums) - 1 // 如果最远位置不小于数组最后一个位置的索引，说明可以到达
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    fmt.Println(canJump([]int{2,3,1,1,4})) // 输出: true
    fmt.Println(canJump([]int{3,2,1,0,4})) // 输出: false
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们需要遍历整个数组一次。
• 空间复杂度：O(1)，我们只使用了两个额外的变量，所以空间复杂度是常数级别。

通过这种方式，我们可以在一次遍历中解决问题，这是最优解。