45. Jump Game II
程序员文章站
2022-06-04 15:44:58
...
题目描述(困难难度)
从数组的第 0 个位置开始跳,跳的距离小于等于数组上对应的数。求出跳到最后个位置需要的最短步数。比如上图中的第 0 个位置是 2,那么可以跳 1 个距离,或者 2 个距离,我们选择跳 1 个距离,就跳到了第 1 个位置,也就是 3 上。然后我们可以跳 1,2,3 个距离,我们选择跳 3 个距离,就直接到最后了。所以总共需要 2 步。
解法一 顺藤摸瓜
leetCode 讨论里,大部分都是这个思路,贪婪算法,我们每次在可跳范围内选择可以使得跳的更远的位置。
如下图,开始的位置是 2,可跳的范围是橙色的。然后因为 3 可以跳的更远,所以跳到 3 的位置。
如下图,然后现在的位置就是 3 了,能跳的范围是橙色的,然后因为 4 可以跳的更远,所以下次跳到 4 的位置。
写代码的话,我们用 end 表示当前能跳的边界,对于上边第一个图的橙色 1,第二个图中就是橙色的 4,遍历数组的时候,到了边界,我们就重新更新新的边界。
public class Jump_Game_II {
public static int jump(int[] nums) {
int end = 0;
int maxPosition = 0;
int steps = 0;
for(int i = 0; i < nums.length - 1; i++){
//找能跳的最远的
maxPosition = Math.max(maxPosition, nums[i] + i);
if( i == end){ //遇到边界,就更新边界,并且步数加一
end = maxPosition;
steps++;
}
}
return steps;
}
public static void main(String args[]) {
int[] nums= {2,1,3,2,1};
int ans=jump(nums);
System.out.println(ans);
}
}
时间复杂度:O(n)。
空间复杂度:O(1)。