跳跃游戏2

分析

个人比起 55 题更难了。这题的重点在于如何进行「贪心」地向后查找。以 [2, 3, 1, 1, 4] 为例： i = 0 时，最大跳跃距离为 2， i = 1 时，最大跳跃距离为 3。因此，我们可以维护一个当前可到达的边界 max_jump。到达边界时，更新边界值并增加跳跃次数。

解答

1
class Solution {
2
public:
3
  int jump(vector<int> &nums) {
4
    auto count = 0;
5
    auto end = 0;
6
    auto max_jump = 0;
7
    auto n = nums.size();
8

9
    for (auto i = 0; i < n - 1; ++i) {
10
      max_jump = max(max_jump, nums[i] + i);
11

12
      if (max_jump >= n - 1)
13
        return count + 1;
14

15
      if (i == end) {
16
        end = max_jump;
17
        count++;
18
      }
19
    }
20

21
    return count;
22
  }
23
};