跳跃游戏 II

题面

给定一个长度为 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 <= 104
• 0 <= nums[i] <= 1000
• 题目保证可以到达 n - 1

分析

• 在每一步跳跃的范围内，尽可能选择能跳得最远的位置，从而保证用最少的步数到达终点

  class Solution {
  public:
      int jump(vector<int>& nums) {
          int range = 0; // 遍历过程中能到达的全局最远距离
          int ans = 0;
          int cur = 0; // 当前跳跃能到达的最远边界
          for (int i = 0; i + 1 < nums.size(); i++) {
              // 更新当前能到达的最远距离
              range = max(i + nums[i], range);
              // 当遍历到当前跳跃的边界时，说明需要进行一次新的跳跃
              if (i == cur) {
                  cur = range;
                  ans++; // 更新下一次跳跃的边界
              }
          }
          return ans;
      }
  };