LeetCode 45.跳跃游戏 II
题目描述
给定一个非负整数数组 nums
,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是跳到最后一个位置(数组的最后一个索引)。你可以选择跳过某些步骤,也可以跳负数。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 从位置 0 跳到 1(跳 1 步),然后从位置 1 跳到 3(跳 3 步)。总共跳了 2 步。
示例 2:
输入: nums = [3,2,1,0,4]
输出: 2
解释: 从位置 0 跳到 1(跳 1 步),然后从位置 1 跳到 3(跳 3 步)。总共跳了 2 步。
提示:
1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
Java 实现代码
class Solution {public int jump(int[] nums) {int step = 0; // 记录跳跃次数int maxReach = 0; // 最远可以到达的位置int end = 0; // 当前可以跳到的最远位置for (int i = 0; i < nums.length - 1; i++) {// 更新最远可以跳到的位置end = Math.max(end, i + nums[i]);// 如果已经到达或超过当前步的终点,则开始下一步if (i == maxReach) {step++;maxReach = end;}}return step;}
}
解题思路
- 贪心算法:使用贪心算法,从左到右遍历数组,每次尝试跳到最远的位置。
- 维护最远位置:使用变量
maxReach
记录当前步可以到达的最远位置,end
记录当前可以跳到的最远位置。- 边界条件:在每次循环中,只有当索引
i
等于maxReach
时,表示已经到达或超过当前步的终点,开始计算下一步。- 终止条件:当遍历到数组的最后一个索引时,返回总的跳跃步数。
复杂度分析
- 时间复杂度:O(n),其中 n 是数组
nums
的长度。最坏情况下需要遍历整个数组。- 空间复杂度:O(1),只需要常数级别的额外空间来存储跳跃次数、最远可以到达的位置和当前可以跳到的最远位置。