跳跃游戏 - Stellar Observer Protocol

579 字

3 分钟

跳跃游戏

2025-08-20

Algorithms

数组

/

贪心

/

动态规划

题目描述#

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

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

解题思路#

贪心策略：
- 维护当前可到达的最远位置 maxReach
- 遍历数组，实时更新最大覆盖范围
实时决策：
- 若当前位置超过当前 maxReach 则失败
- 若 maxReach 已覆盖终点则提前终止
边界处理：
- 空数组直接返回false
- 单元素数组默认成功
动态更新：
- maxReach = max(maxReach, i + nums[i])
- 仅需遍历到当前 maxReach 位置

关键洞察#

覆盖范围原理：
- 能否到达终点 ⇔ 最大覆盖范围是否包含终点
- 无需考虑具体跳跃路径
贪心最优性：
- 局部最大覆盖保证全局可达性
- 提前终止优化性能
位置依赖性：
- 当前位置可达性依赖于前一状态
- 不可到达的位置立即失败
空间优化：
- 仅需单个变量存储覆盖范围
- 避免使用额外数组存储状态

复杂度分析#

指标	说明
时间复杂度	O(n)：最坏情况遍历整个数组
空间复杂度	O(1)：仅使用常数级别额外空间

代码实现#

1
const canJump = (nums) => {
2
    if (nums.length === 0) return false;
3
    if (nums.length === 1) return true;
4
    let maxReach = 0;
5
    for (let i = 0; i < nums.length; i++) {
6
        // 当前位置已超出可达范围
7
        if (i > maxReach) return false;
8
        // 更新最远可达位置
9
        maxReach = Math.max(maxReach, i + nums[i]);
10
        // 已覆盖终点则提前终止
11
        if (maxReach >= nums.length - 1) return true;
12
    }
13
    return false;
14
};