题目概览给定一个长度为n的0 索引整数数组nums。初始位置在下标 0。每个元素nums[i]表示从索引i向后跳转的最大长度。换句话说如果你在索引i处你可以跳转到任意(i j)处0 j nums[i]且i j n返回到达n - 1的最小跳跃次数。测试用例保证可以到达n - 1。示例 1:输入:nums [2,3,1,1,4]输出:2解释:跳到最后一个位置的最小跳跃数是2。 从下标为 0 跳到下标为 1 的位置跳1步然后跳3步到达数组的最后一个位置。示例 2:输入:nums [2,3,0,1,4]输出:2提示:1 nums.length 10^40 nums[i] 1000题目保证可以到达n - 1来源45. 跳跃游戏 II - 力扣LeetCode解题分析方法贪心令当前索引为 i那么在 [ i, nums[ i ] i ] 范围内我们都可以跳跃且跳跃次数只 1。要想用最小次数到达终点我们的跳跃距离要保证足够大因此我们在 [ i, nums[ i ] i ] 需要找到眺的最远的索引作为下一个跳板令该索引为 j即 nums[ j ] j 需要最大。因此我们可以定义一个变量 minJumpTimes 存储跳跃次数maxDepth 存储当前最大跳跃距离起始索引为 start该索引能跳到的最大索引为 end遍历 [start, end) 之间的跳跃距离找到最大的距离 maxDepth将 maxDepth 作为下一次起跳能跳到的最大索引下一次起跳的初始索引就为 end每次遍历 minJumpTimes 加一直到 end n 返回 minJumpTimes 即可。时间复杂度O(n)空间复杂度O(1)class Solution { public int jump(int[] nums) { int n nums.length; int start 0, end 1, minJumpTimes 0; while(end n) { int maxDepth 0; for (int i start; i end; i) { maxDepth Math.max(maxDepth, nums[i] i); } minJumpTimes; start end; end maxDepth 1; } return minJumpTimes; } }