题目描述

picture 0

解题思路

跳跃游戏问题分析

题目理解

• 从数组第一个下标（索引0）开始
• nums[i] 表示在位置i可以跳跃的最大长度
• 目标：判断是否能到达最后一个下标（索引n-1）
• 只需要判断可行性，不需要输出具体路径

贪心策略分析

核心思想

维护一个变量记录当前能够到达的最远位置。

关键洞察：如果我们能到达位置i，那么我们也能到达位置0到i之间的所有位置。

贪心策略

1. 初始化 max_reach = 0（当前能到达的最远位置）
2. 遍历数组的每个位置i：
   • 如果 i > max_reach，说明当前位置无法到达，直接返回false
   • 否则，更新 max_reach = max(max_reach, i + nums[i])
   • 如果 max_reach >= n-1，说明已经能到达最后位置，返回true
3. 遍历结束后，检查是否能到达最后位置

为什么贪心正确？

贪心选择性质：

• 在每个位置i，我们都尽可能扩展能到达的最远距离
• 如果存在一条路径能到达终点，那么我们的贪心策略一定不会错过
• 因为我们总是维护着所有可能路径中能到达的最远位置

最优子结构：

• 能到达位置i的最优解包含了能到达位置0到i-1的最优解
• 每个位置的决策只依赖于之前能到达的最远位置

算法优化

实际上，我们只需要遍历到 min(max_reach, n-1) 即可，因为超出这个范围的位置我们都无法到达。

算法步骤

1. 初始化 max_reach = 0
2. 遍历i从0到n-1：
   • 如果 i > max_reach，返回false
   • 更新 max_reach = max(max_reach, i + nums[i])
   • 如果 max_reach >= n-1，返回true
3. 返回 max_reach >= n-1

时间复杂度分析

• 时间复杂度：O(n) - 最多遍历一次数组
• 空间复杂度：O(1) - 只使用常数额外空间

Python代码实现

def canJump(nums):
    """
    判断是否能跳跃到数组最后一个位置
    
    Args:
        nums: List[int] - 每个位置的最大跳跃长度
    
    Returns:
        bool - 是否能到达最后一个位置
    """
    if not nums:
        return True
    
    n = len(nums)
    if n == 1:
        return True
    
    max_reach = 0  # 当前能到达的最远位置
    
    for i in range(n):
        # 如果当前位置无法到达，直接返回false
        if i > max_reach:
            return False
        
        # 更新能到达的最远位置
        max_reach = max(max_reach, i + nums[i])
        
        # 如果已经能到达最后位置，提前返回
        if max_reach >= n - 1:
            return True
    
    return max_reach >= n - 1

# 测试用例
if __name__ == "__main__":
    # 测试用例1
    nums1 = [2, 3, 1, 1, 4]
    print(f"输入: {nums1}")
    print(f"输出: {canJump(nums1)}")  # 期望输出: True
    
    # 测试用例2
    nums2 = [3, 2, 1, 0, 4]
    print(f"输入: {nums2}")
    print(f"输出: {canJump(nums2)}")  # 期望输出: False
    
    # 边界测试
    nums3 = [0]
    print(f"输入: {nums3}")
    print(f"输出: {canJump(nums3)}")  # 期望输出: True
    
    nums4 = [0, 1]
    print(f"输入: {nums4}")
    print(f"输出: {canJump(nums4)}")  # 期望输出: False
    
    nums5 = [1, 0, 1, 0]
    print(f"输入: {nums5}")
    print(f"输出: {canJump(nums5)}")  # 期望输出: False

算法执行过程示例

示例1：[2, 3, 1, 1, 4]

i=0: max_reach = max(0, 0+2) = 2
i=1: max_reach = max(2, 1+3) = 4 >= 4, 返回True

示例2：[3, 2, 1, 0, 4]

i=0: max_reach = max(0, 0+3) = 3
i=1: max_reach = max(3, 1+2) = 3
i=2: max_reach = max(3, 2+1) = 3
i=3: max_reach = max(3, 3+0) = 3
i=4: i=4 > max_reach=3, 返回False

关键洞察

这个贪心算法的精髓在于：

1. 状态简化：不需要记录具体路径，只需要知道最远能到达哪里
2. 早期终止：一旦发现无法到达某个位置，立即返回false
3. 最优覆盖：维护的最远距离包含了所有可能路径的信息

这种方法比BFS或DFS更高效，避免了重复计算和不必要的状态存储。

注意事项与题目启发

需要注意的问题

1. 边界条件处理

if not nums:
    return True
if n == 1:
    return True

• 空数组：虽然题目保证非负整数数组，但防御性编程仍要考虑
• 单元素数组：起始位置就是终点，直接返回True
• 第一个元素为0：如果数组长度>1且nums[0]=0，肯定无法前进

2. 循环范围的理解

• 循环必须遍历到 n-1（最后一个位置），因为需要检查是否能到达终点
• 不能提前在 i < n-1 时停止，否则可能漏掉关键更新

3. 条件判断的顺序

if i > max_reach:  # 先检查是否可达
    return False
max_reach = max(max_reach, i + nums[i])  # 再更新最远距离

• 必须先检查可达性，再更新max_reach
• 如果顺序颠倒，会在不可达位置错误地更新max_reach

4. 提前终止的时机

• 当 max_reach >= n-1 时可以立即返回True
• 但要注意这个检查必须在更新max_reach之后进行

5. 数据类型和溢出

• 虽然Python不会溢出，但在其他语言中 i + nums[i] 可能溢出
• 题目保证非负整数，所以不会出现负数跳跃的异常情况

6. 算法逻辑误区

• 不是找具体路径：只需要判断可行性，不需要记录跳跃步骤
• 不是动态规划：虽然有状态转移的思想，但贪心更简洁高效
• 不是BFS/DFS：不需要探索所有可能的跳跃组合

7. 测试用例覆盖

需要考虑多种边界情况：

• [0] → True（单元素）
• [0,1] → False（第一步就卡住）
• [1,0,1,0] → False（中间卡住）
• [2,0,0] → True（一步到位）
• [1,1,1,1] → True（逐步前进）

题目的启发

1. 贪心算法的本质

• 状态压缩：将复杂的路径问题简化为"最远能到哪里"的单一状态
• 局部最优=全局最优：每次扩展最远距离的选择不会影响最终结果
• 反直觉的简洁性：看似需要复杂搜索的问题，其实有极其简洁的解法

2. 问题建模的思维方式

• 抽象能力：将具体的跳跃动作抽象为可达范围的扩展
• 逆向思维：不关心"怎么跳"，只关心"能跳多远"
• 覆盖思想：用一个区间覆盖所有可能的到达位置

3. 算法设计的经典模式

这个问题展示了"可达性问题"的经典解法：

• 维护当前能达到的最远边界
• 在边界内进行状态更新
• 边界扩展到目标即成功

类似的模式还出现在：

• 区间覆盖问题
• 加油站问题
• 字符串分割问题

4. 实际应用价值

• 网络路由：判断数据包是否能从源到达目的地
• 游戏设计：关卡设计中的可达性验证
• 资源分配：判断资源是否足够支撑到最终目标
• 路径规划：简化版的路径可行性判断

5. 编程思维的培养

• 从复杂到简单：学会识别问题的本质，避免过度设计
• 边界思维：特别关注起始状态和终止条件
• 效率意识：O(n)解法比O(n²)的暴力解法优雅得多

6. 算法复杂度的认知

• 时间效率：线性时间解决看似需要指数时间的问题
• 空间效率：常数空间，无需额外数据结构
• 可扩展性：算法容易扩展到变种问题（如跳跃游戏II）

7. 扩展思考方向

这个问题有很多有趣的变种：

• 跳跃游戏II：求最少跳跃次数（同样用贪心）
• 带障碍的跳跃：某些位置不能停留
• 双向跳跃：可以向前或向后跳
• 能量消耗：每次跳跃消耗能量，需要管理能量值
• 多维跳跃：在二维或三维网格中跳跃

8. 面试价值

• 经典程度：这是贪心算法的经典面试题
• 考察维度：
  • 问题分析能力
  • 算法设计能力
  • 边界处理能力
  • 代码实现能力
• 延伸性强：可以自然过渡到其他贪心或动态规划问题

9. 学习方法论

• 理解本质：不要死记硬背代码，要理解为什么维护最远距离就足够了
• 手动验证：通过小例子手动模拟算法执行过程
• 对比思考：与BFS、DFS等其他解法对比，理解贪心的优势

这个题目完美诠释了"简单即是美"的编程哲学，它告诉我们：有时候最优雅的解决方案往往来自于对问题本质的深刻理解，而不是复杂的算法堆砌。