🍥

Hang Zhang

genius.

Data Structure and Algorithm

Jump Game

55. 跳跃游戏

分析

维护最远可达位置：
- 使用变量 i 表示当前最远可达的位置
- 初始位置为 0
逐步检查跳跃能力：
- 遍历数组，当前下标为 j，检查是否可以到达：
  - 如果 i < j，说明无法继续前进，返回 false
- 更新最远可达位置：
  - i = max(i, j + nums[j]
终止条件：
- 遍历结束后，若能始终更新 i 使其覆盖整个数组，返回 true

时间复杂度

遍历数组一次，时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution
{
public:
    bool canJump(vector<int>& nums)
    {
        int i = 0; // 当前最远可达位置
        for (int j = 0; j < nums.size(); ++j)
        {
            if (i < j)  // 如果无法覆盖当前位置
                return false;
            i = std::max(i, j + nums[j]); // 更新最远可达位置
        }
        return true; // 如果能够遍历完成，返回 true
    }
};