45. 跳跃游戏 II

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

思路

BFS 层数思想。维护当前层最远位置 curEnd 和下一层最远位置 farthest。 当 i == curEnd 时换层，step++，curEnd = farthest。

代码

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), step = 0, curEnd = 0, farthest = 0;
        for (int i = 0; i < n - 1; ++i) {
            farthest = max(farthest, i + nums[i]);
            if (i == curEnd) { ++step; curEnd = farthest; }
        }
        return step;
    }
};

复杂度

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

易错 / 回顾

• 循环到 n - 1（最后一个位置不需要再跳一次）
• step 增量时机：i 抵达本层右界
• 题目保证可达，所以无需判越界