55. 跳跃游戏

难度：🟡 Medium | 标签：贪心 | 状态：⬜ LeetCode 链接

思路

维护「能到达的最远下标」reach。 遍历时若 i > reach 则不可达；否则用 i + nums[i] 更新 reach。

代码

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

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• 一旦 reach >= n - 1 可提前返回
• 不要 DFS / DP，贪心一次扫即可
• 跟 45 不同：本题判可否，45 求最少步数