45. 跳跃游戏 II

45. 跳跃游戏 II - 力扣（LeetCode）

class Solution {
public:
  int jump(vector<int>& nums) {
    int Jumps = 0;
    int PrevRightmost = 0;
    int Rightmost = 0;
    // The problem ensures that we can always jump to the last one, so there's
    // no need to check the last element anymore.
    for (int i = 0; i < nums.size() - 1; ++i) {
      Rightmost = std::max(Rightmost, i + nums[i]);
      if (i == PrevRightmost) {
        // We've collected all possible Jumps inside [0, PrevRightmost]. It's
        // time that we choose the Rightmost one and jump!
        PrevRightmost = Rightmost;
        ++Jumps;
      }
    }
    return Jumps;
  }
};

评论区里的这个解释非常好，尤其是代码注释当中的这句：

总体策略：在当前索引位置下，跳跃一步能到达的所有位置的边界内，选择那个下次能跳的更远的那个位置

这样你就能理解为什么我们直到 i == PrevRightmost 的时候才往后跳，并且更新 Jumps 了——因为我们已经考察完了在 PrevRightmost 之前的所有可能的最大跳跃距离，并通过 max() 记录在了 Rightmost 当中。

不考虑 i == nums.size() - 1 是为了防止类似于

$$ [1\ 1] $$

的这种情况。这种情况下你会发现你在 i = 0 时跳过第一次之后，PrevRightmost 刚好等于 1 == nums.size() - 1。但是当下个循环 i = 1 时，我们其实已经到达了终点，然而 i == PrevRightmost 的判断会导致我们不必要地自增了一个 Jumps。

二刷

class Solution {
public:
  int jump(vector<int>& nums) {
    int Result = 0;
    int Rightmost = 0;
    int End = 0;

    for (int i = 0; i < nums.size() - 1; ++i) {
      Rightmost = max(i + nums[i], Rightmost);
      if (i == End) {
        ++Result;
        End = Rightmost;
      }
    }
    return Result;
  }
};

背吧背吧，至少55. 跳跃游戏三刷真写出来了，这个乍一想想不到也无所谓了。