题目:
给定一个长度为 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]
。
思路:每次在上次能跳到的范围(end)内选择一个能跳的最远的位置作为下次的起跳点
代码:
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int end = 0; // 上次跳跃可达范围右边界(下次的最右起跳点,不一定从这跳)
int maxPosition = 0; // 目前能跳到的最远位置
int steps = 0; // 跳跃次数
for (int i = 0; i < n - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
steps++; // 进入下一次跳跃
}
}
return steps;
}
}
性能:时间复杂度O(n) 空间复杂度O(1)