贪心----3. 跳跃游戏 II

45. 跳跃游戏 II - 力扣（LeetCode）

/**

        维护变量:

                max_reachable,遍历过的元素的最远可达位置

                end,当前区间终点(随max_reachable变化)

        遍历过程:

                遍历时迭代遍历过的元素最远可达位置,利用end记录当前区间终点(随max_reachable变化)

                当移动至end即当前区间终点时,需要更新end为新的max_reachable即下一个区间终点,同时步数+1

                直到end >= nums.length - 1,代表已经可以到达终点,可提前结束

                即,在遍历过程中将数组分为了不同的区间,当移动至end时当前区间结束,更新下一个区间终点为max_reachable,区间数即为最少需要的步数

                区间代表每步最多移动的位置

*/

class Solution {/**维护变量:max_reachable,遍历过的元素的最远可达位置end,当前区间终点(随max_reachable变化)遍历过程:遍历时迭代遍历过的元素最远可达位置,利用end记录当前区间终点(随max_reachable变化)当移动至end即当前区间终点时,需要更新end为新的max_reachable即下一个区间终点,同时步数+1直到end >= nums.length - 1,代表已经可以到达终点,可提前结束即,在遍历过程中将数组分为了不同的区间,当移动至end时当前区间结束,更新下一个区间终点为max_reachable,区间数即为最少需要的步数区间代表每步最多移动的位置*/public int jump(int[] nums) {int maxReachable = 0;int end = 0;int jumps = 0;for(int i = 0; i < nums.length - 1; i++) {maxReachable = Math.max(maxReachable, i + nums[i]);if(i == end) {end = maxReachable;jumps++;}if(end >= nums.length - 1) {break;}}return jumps;}
}