原题地址：45. 跳跃游戏 II - 力扣（LeetCode）
题目描述
给定一个长度为
n的 0 索引整数数组nums。初始位置为nums[0]。每个元素
nums[i]表示从索引i向前跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳转到任意nums[i + j]处:
0 <= j <= nums[i]i + j < n返回到达
nums[n - 1]的最小跳跃次数。生成的测试用例可以到达nums[n - 1]。示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是2。从下标为 0 跳到下标为 1 的位置，跳 1步，然后跳 3步到达数组的最后一个位置。示例 2:
输入: nums = [2,3,0,1,4] 输出: 2
解题思路
问题描述
给定一个数组nums，其中每个元素表示可以跳跃的最大步数，目标是从数组的第一个位置跳到最后一个位置，求出最少的跳跃次数。贪心算法思想
- 从后往前思考，目标是找到从最后一个位置可以跳到的位置，逐步回溯到起点。
- 每次遍历数组，寻找一个可以直接跳到当前位置的最远索引，并将其作为新的目标。
- 每找到一个新的目标索引，步数 (
steps) 增加一次，直到目标索引回溯到起点。
源码实现
class Solution {public int jump(int[] nums) {// 初始化目标位置为最后一个索引int position = nums.length - 1;// 初始化跳跃次数int steps = 0;// 当目标位置还未回到起点时，继续寻找跳跃路径while (position > 0) {// 从起点到当前位置遍历，寻找一个能跳到目标位置的索引for (int i = 0; i < position; i++) {// 如果索引 i 能跳到目标位置if (i + nums[i] >= position) {// 将目标位置更新为索引 iposition = i;// 增加一次跳跃次数steps++;// 找到后立即退出内层循环，进行下一步回溯break;}}}// 返回跳跃的总次数return steps;}
}
复杂度分析
时间复杂度：
- 外层循环的次数等于最终的跳跃次数（
steps），最坏情况下为O(n)。- 内层循环每次遍历目标位置之前的所有索引，最坏情况下为
O(n)。
因此，时间复杂度为O(n^2)。空间复杂度：
- 该算法只使用了常数个变量（
position和steps），没有额外的空间开销。
空间复杂度为O(1)。