leetcode 困难 第45题 跳跃游戏Ⅱ

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/jump-game-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

第一种方法，慢的，两层循环。

class Solution { public int jump(int[] nums) { int step = 0 ; int position = nums.length - 1 ; while(position > 0){ for(int i = 0 ; i < position ; i ++){ if(nums[i] + i >= position){ step ++ ; position = i ; break ; } } } return step ; } }

主要思路是：从后往前检索，找到那个离最后元素最远的，又能符合条件的元素的位置（内层循环，从前往后找到符合条件的位置），然后，把他最为新的最后的元素。再继续循环。

第二种方法：

class Solution { public int jump(int[] nums) { int step = 0 ; int end = 0 ; int maxposition = 0 ; for(int i = 0 ; i < nums.length - 1 ; i ++ ){ maxposition = Math.max(maxposition,nums[i] + i); if(i == end){ end = maxposition ; step ++ ; } } return step ; } }

这种方法是一层循环 。 从前往后检索。用找到每一个元素能跳的最远的地方，记为边界，然后从当前位置开始遍历数组（找到再该区间内的元素，能到达的最远的位置），到达边界后，更新边界为前面说的最远的位置，并且把step加一。

困难难度的题，有点不好理解。还需要再看看。