跳跃游戏 II

题意

给定跳跃数组（保证可达），求最少跳跃次数。

思路

用 BFS 层次遍历的思想：每跳一步，当前"层"的范围是 [l, r]，下一层最远可达 next = max(i + nums[i]) for i in [l, r]。当 r 到达末尾时停止。

每层对应一次跳跃，next 是下一层的右边界。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().jump(a) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
from typing import List


class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        jumps = curEnd = farthest = 0
        for i in range(n - 1):
            farthest = max(farthest, i + nums[i])
            if i == curEnd:
                jumps += 1
                curEnd = farthest
        return jumps


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(Solution().jump(a))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。

总结

最少跳跃次数 = BFS 层数。每层扩展最远可达位置，贪心选择下一层边界。与跳跃游戏 I 的区别是：I 只判断可达性，II 要最小化步数。

目录

题意

思路

代码

复杂度

总结