给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。使用最少跳跃次数达到数组最后一个位置。
输入: [2,3,1,1,4]
输出: 2
解释: 从位置 0 到位置 1 跳 1 步, 然后跳 3 步到达最后一个位置。
解题思路：
贪心算法
代码：
public int jump(int[] nums) {
int length = nums.length;
int end = 0, maxPosition = 0, step = 0;
for (int i = 0; i < length - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (end == i) {
end = maxPosition;
step++;
}
}
return step;
}
复杂度分析：
- 时间复杂度：O(N)，需要遍历数组长度
- 空间复杂度：O(1)，只需要常数空间
网友评论