45. 跳跃游戏 II

       
题目给定一个数组，每个元素表示该位置能向后跳跃的最大步数（例如 nums = j 表示从下标 i 最多可以跳到 i + j）。要求盘算从数组起始位置到达末端（下标 n-1）所需的最少跳跃次数。
解题思绪接纳贪默算法：在当前可到达范围内，尽可能延长跳跃。具体来说：

• 维护当前能到达的最远位置
  
• 当遍历到当前步数能到达的边界时，才举行跳跃
  
• 每次跳跃时更新能到达的新边界 这样就能确保用最少的跳跃次数到达终点。
  

2. class Solution {
3. public:
4.     int jump(vector<int>& nums) {
5.         int n = nums.size();
6.         int mx_right = 0;//当前能到的最右端
7.         int cur_right = 0;//当前的最右端
8.         int ans = 0;
9.         for (int i = 0;i < n - 1;i++) {
10.             mx_right = max(mx_right,nums[i] + i);
11.             if (cur_right == i) {
12.                 cur_right = mx_right;
13.                 ans++;
14.             }
15.         }
16.         return ans;                          
17.     }
18. };

复制代码

        时间复杂度：O(n)
        空间复杂度：O(1)

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

继续阅读请点击广告