Medium

题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1，然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 10⁴
  • 0 <= nums[i] <= 10⁵

解题思路

这道题有两种主要解法：动态规划和贪心算法。

方法一：动态规划 用 dp[i] 表示是否能到达位置 i。状态转移方程为：dp[i] = true 当存在某个 j < i 使得 dp[j] = true 且 j + nums[j] >= i。时间复杂度 O(n²)，空间复杂度 O(n)。

方法二：贪心算法（推荐） 核心思想是维护一个变量 maxReach 记录当前能到达的最远位置。从左到右遍历数组，对于每个位置 i：

  1. 如果 i > maxReach，说明无法到达位置 i，返回 false
  2. 否则更新 maxReach = max(maxReach, i + nums[i])
  3. 如果 maxReach >= nums.length - 1，说明能到达最后一个位置

贪心策略的正确性在于：如果能到达位置 i，那么一定能到达 [0, maxReach] 范围内的所有位置。我们只需要确保每一步都能让我们走得更远即可。

这种方法时间复杂度 O(n)，空间复杂度 O(1)，是最优解法。

代码实现

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = max(maxReach, i + nums[i]);
            if (maxReach >= nums.size() - 1) {
                return true;
            }
        }
        return true;
    }
};

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0
        for i in range(len(nums)):
            if i > max_reach:
                return False
            max_reach = max(max_reach, i + nums[i])
            if max_reach >= len(nums) - 1:
                return True
        return True

public class Solution {
    public bool CanJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.Max(maxReach, i + nums[i]);
            if (maxReach >= nums.Length - 1) {
                return true;
            }
        }
        return true;
    }
}

var canJump = function(nums) {
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            return false;
        }
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) {
            return true;
        }
    }
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型贪心算法动态规划
时间复杂度O(n)O(n²)
空间复杂度O(1)O(n)

相关题目