45. 跳跃游戏 II

题目给定一个数组，每个元素表示该位置能向后跳跃的最大步数（例如 nums[i] = j 表示从下标 i 最多可以跳到 i + j）。要求计算从数组起始位置到达末尾（下标 n-1）所需的最少跳跃次数。

解题思路采用贪心算法：在当前可到达范围内，尽可能延迟跳跃。具体来说：

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

class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();int mx_right = 0;//当前能到的最右端int cur_right = 0;//当前的最右端int ans = 0;for (int i = 0;i < n - 1;i++) {mx_right = max(mx_right,nums[i] + i);if (cur_right == i) {cur_right = mx_right;ans++;}}return ans;                          }
};

        时间复杂度：O(n)

        空间复杂度：O(1)