力扣 跳跃游戏 II

贪心算法，存下每一步的最远，去达到全局的最小跳跃次数。
题目

从题中要达到最少次数，肯定是每一步尽可能走远一点。但注意j被限定了范围，这种不消想每一步遍历时肯定选最大的num，但要注意，题中是可以到达不是刚好到达，因此最后一步只要大于最后一个数都是可以的。从第一个数开始遍历，每一步贪心去选最远的距离，然后每个数都存下一个可达到的最远距离便于更新，由于贪心每一次都是基于当前数的最优，并不是全局最优。
时间复杂度： O(n)，空间复杂度： O(1)。

1. class Solution {
2.     public int jump(int[] nums) {
3.         int step=0,end=0,furthest=0;
4.         for(int i=0; i<nums.length-1;i++){  
5.             furthest = Math.max(furthest, i+nums[i]);  //dp每个i，记录每个位置能达到的最远距离
6.             if(i==end){  //i遍历到上个起跳点能到的最远距离
7.                 end = furthest;  //更新到下一步要跳到的位置，注意这里跳的最远距离由i前面的数贪心选出来的
8.                 step++;  //来到这里就加了一步
9.             }
10.         }
11.         return step;
12.         
13.     }
14. }

复制代码

动态规划是存一个要维护状态的dp数组，每次的状态由上几个状态更新得到，这题用dp会很慢。而贪心策略在于，每一步都存下最优状态便于后续的更新。
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。