题目

解法：贪心

思路

贪心算法，维护当前能到达的最远位置。

该方法正确性的核心在于贪心选择策略：在每一步都尽可能跳得最远。维护的不变量是’所有小于等于 i 的位置都是可达的’。如果 i > max_reach，说明位置 i 不可达，那么 i 之后的所有位置也无法到达，因为无法跳过这个断点。反之，只要能够遍历到数组末尾，就说明每个位置都是可达的，因此可以到达最后一个下标。

• Step 1: 初始化 max_reach = 0，表示在起点能到达的最远位置
• Step 2: 遍历数组，对于每个位置 i
• Step 3: 如果 i > max_reach，说明无法到达位置 i，返回 false
• Step 4: 更新 max_reach = max(max_reach, i + nums[i])
• Step 5: 如果遍历完成，说明可以到达最后一个下标，返回 true

复杂度

• 时间复杂度: $O(n)$，其中 n 是数组长度。只需一次线性遍历。
• 空间复杂度: $O(1)$，仅使用常数级别的额外空间。

代码

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