跳跃游戏

题意

给定跳跃数组，判断能否到达末尾。

思路

维护 max_reach 表示当前最远可达位置。扫描到 i 时，若 i > max_reach 说明无法到达位置 i，返回 false。否则更新 max_reach = max(max_reach, i + nums[i])。

max_reach 是单调不减的扫描不变式：每个可达位置都能进一步扩展可达范围。

代码

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#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool canJump(vector<int> &nums) {
        int reach = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            if (i > reach)
                return false;
            reach = max(reach, i + nums[i]);
        }
        return true;
    }
};

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().canJump(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#!/usr/bin/env python3
from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reach = 0
        for i, x in enumerate(nums):
            if i > reach:
                return False
            reach = max(reach, i + x)
        return True


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


if __name__ == "__main__":
    main()

复杂度

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

总结

跳跃可达性判断是贪心的典型：最远可达位置单调不减，扫描一遍即可。无需回溯或动态规划。

目录

题意

思路

代码

复杂度

总结