vvrf / DSA.log

问题拆解

站在数组开头，nums[i] 是在下标 i 处最多能往前跳的步数，问能否到达最后一个下标。

按“路径”去想会走弯路：从每个位置枚举所有跳法做 DFS 是指数级的，加记忆化的 DP 也要 O(n²)。但这题只问“能不能到”，不问怎么到——这类可达性判断往往不需要保留路径。

关键观察是可达范围是连续的：如果能到下标 j，那 0 到 j 之间的每个下标都能到（跳远了可以少跳几步）。所以全部状态可以压缩成一个数：当前的最远可达下标 furthest。从左到右扫，每个还够得着的位置都用 i + nums[i] 去扩展它。

可达集合是一段连续前缀，于是“能到哪些点”这个集合问题坍缩成“右边界在哪”这个单值问题——贪心成立的根源就在这里。

一路维护最远可达边界

public boolean canJump(int[] nums) {
    int furthest = 0; // 目前能到达的最远下标
    for (int i = 0; i < nums.length; i++) {
        if (i > furthest) {
            return false; // 当前位置本身就够不着，后面更不可能
        }
        furthest = Math.max(furthest, i + nums[i]);
        if (furthest >= nums.length - 1) {
            return true;
        }
    }
    return true;
}

def canJump(nums: List[int]) -> bool:
    furthest = 0  # 目前能到达的最远下标

    for i, step in enumerate(nums):
        if i > furthest:
            return False  # 当前位置本身就够不着，后面更不可能
        furthest = max(furthest, i + step)
        if furthest >= len(nums) - 1:
            return True

    return True

func canJump(nums []int) bool {
    furthest := 0 // 目前能到达的最远下标
    for i, step := range nums {
        if i > furthest {
            return false // 当前位置本身就够不着，后面更不可能
        }
        furthest = max(furthest, i+step)
        if furthest >= len(nums)-1 {
            return true
        }
    }
    return true
}

pub fn can_jump(nums: Vec<i32>) -> bool {
    let mut furthest = 0usize; // 目前能到达的最远下标
    for (i, &step) in nums.iter().enumerate() {
        if i > furthest {
            return false; // 当前位置本身就够不着，后面更不可能
        }
        furthest = furthest.max(i + step as usize);
        if furthest >= nums.len() - 1 {
            return true;
        }
    }
    true
}

i > furthest 这个判断必须放在更新 furthest 之前：一个自己都到不了的位置，它的 nums[i] 是无效信息，不能拿来扩展边界。漏掉这个顺序，[3, 2, 1, 0, 4] 这种被 0 卡死的用例就会误判为 true——下标 4 够不着，却用它的值把边界撑了过去。

再解释一下为什么贪心不会漏解。担心的场景是：某条“绕路”的跳法能到终点，而 furthest 没覆盖到。但 furthest 取的是所有可达位置扩展量的最大值，任何合法跳法经过的每个落点都在 furthest 之内，它下一跳的终点自然也被 max 收进去了——furthest 是所有跳法可达范围的上确界，不存在漏网的路径。

复杂度

指标	复杂度	原因
时间	`O(n)`	单次遍历，每个下标处理一次
空间	`O(1)`	状态只有一个边界值

可以迁移的模式

只问“可行与否”不问方案时，先试着把状态压成一两个聚合量，而不是老实做 DP；
“可达范围连续”是把集合问题压成边界问题的通行证，区间合并、加油站类题目里反复出现；
贪心的正确性论证：证明维护的量是所有方案的上界（或下界），任何解都逃不出它。

姊妹题 45（跳跃游戏 II）问最少跳几次，同一个边界思想再分层推进即可，值得接着做。