45.跳跃游戏 ||
- 跳跃游戏 II
难度困难547
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
从后往前查找-贪心
/**反向查找出发位置
跳跃游戏 可以通过贪心算法来完成，可以从前往后 或者 从后往前，通过获取局部最优解
来解决全局最优解。
从nums.length-1位置 查找之前的一个元素是否能到达，如果可以，遍历数组 从0开始到这个位置。
找出最大值，依序查找，每次选取最大的步数，也就是局部最优解，而最优解，就可以决定全局是一个最优解
time : O(N^2) 当数组中都是相同的数字，需要查找N^2次
space : O(1)
break 跳出循环 continue 结束本次循环 继续下次循环
*/
public int jump(int[] nums) {
if(nums == null || nums.length == 0){
return -1;
}
int steps = 0;//需要跳跃的次数
int position = nums.length-1;
while(position > 0){
for(int i=0;i<position;i++){
if(nums[i]+i>=position){//可以到达
position = i;
steps++;
break;
}
}
}
return steps;
}
从前往后查找-贪心
/*
刚才从后往前推 对于特定的相同的数组，需要遍历O(N^2)次 时间复杂度比较高。
我们换一个思路 从前往后推。[2,3,1,1,4]
steps>记录次数 end>记录当前步长可以走的界限。
比如 从0 位置出发，end = 2 在0位置2步内找到最大值。最大为3，调到3上
在end=3位置查找最大值 发现可以跳出。因此结束。
ps：此处 我们没有跳跃到数组的末尾位置，因此当可以跳出的时候只会大于或等于。
time : O(n) space :O(1)
*/
public int jump(int[] nums) {
if(nums == null || nums.length == 0){
return -1;
}
int steps = 0;
int end = 0;//当前可以跳跃的最大步长
int maxLength = 0;
for(int i= 0;i<nums.length-1;i++){
maxLength = Math.max(maxLength,nums[i]+i);
if(end == i){ //end == i 其实比较的就是在最大步长内 是否会有一个更大的步长
end = maxLength;
steps++;
}
}
return steps;
}