Leetcode|中等|区间贪心|45. 跳跃游戏II

贪心算法

class Solution {
public:
    int jump(vector<int>& nums) {
        int size = nums.size();
        // 当前覆盖终点索引
        int cover = 0;
        int fastTarget = 0, count = 0; 
        // 注意：i∈[0, size - 2]
        for (int i = 0; i < size - 1; i++) {
            fastTarget = max(fastTarget, i + nums[i]);
            // 到达当前覆盖终点时，计数器+1，准备遍历下一段覆盖
            if (i == cover) {
                count++;
                cover = fastTarget;
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

致谢

图片来源于「代码随想录」公众号，欢迎大家关注这位大佬的公号