Jupm Game II

45. 跳跃游戏II

分析

核心思想：使用贪心算法模拟跳跃过程，按层次遍历的思想解决问题
- 当前位置的覆盖范围：表示当前跳跃次数能够到达的最远位置
- 下一次跳跃的覆盖范围：表示增加一次跳跃后能够到达的最远位置
关键变量：
- cur：当前处理的位置。
- dist：当前跳跃次数能够到达的最远位置。
- next：下一跳能够到达的最远位置。
跳跃过程：
- 初始化跳跃次数 res = 0，起点为 cur = 0
- 在当前跳跃的范围内（从 cur 到 dist），计算下一跳的最远位置 next
- 当 dist 超过或等于数组最后一个位置时，结束跳跃。
步数增加：
- 每遍历完当前跳跃的范围时，更新到下一跳的最远位置 dist = next，并增加跳跃次数 res

时间复杂度

每个位置最多访问一次，因此时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
{
public:
    int jump(vector<int>& nums)
    {
        int res = 0;       // 跳跃次数
        int cur = 0;       // 当前处理的位置
        int dist = 0;      // 当前跳跃的覆盖范围
        while (dist < nums.size() - 1)
        {
            int next = 0;  // 下一跳的覆盖范围
            // 遍历当前跳跃范围
            while (cur <= dist)
            {
                next = std::max(next, cur + nums[cur]);  // 更新下一跳的最远范围
                ++cur;
            }
            dist = next;   // 更新跳跃范围
            ++res;         // 跳跃次数加一
        }
        return res;
    }
};