题解链接

Leetcode 45.跳跃游戏Ⅱ-原题链接

题目描述

给定一个长度为 $n$ 的 $0$ 索引整数数组 $nums$。初始位置在下标 $0$。

每个元素 $nums[i]$ 表示从索引 $i$ 向后跳转的最大长度。换句话说，如果你在索引 $i$ 处，你可以跳到任意 $(i + j)$ 处：

• $0 \leq j \leq nums[i]$ 且
• $i + j < n$

返回到达 $n - 1$ 的最小跳跃次数。测试用例保证可以到达 $n - 1$。

输入描述

第一行输入一个整数 $n$，表示数组的长度。

第二行输入 $n$ 个整数，表示数组 $nums$。

输出描述

输出一个整数，表示到达下标 $n - 1$ 的最小跳跃次数。

样例 1

输入：

5
2 3 1 1 4

输出：

2

解释：

跳到最后一个位置的最小跳跃数是 $2$。从下标 $0$ 跳到下标为 $1$ 的位置，跳 $1$ 步，然后跳 $3$ 步到达数组的最后一个位置。

样例 2

输入：

5
2 3 0 1 4

输出：

2

数据范围

保证可以到达下标 $n - 1$。