content: package question0045_jump_game_ii;
  
  /**
   * https://leetcode-cn.com/problems/jump-game-ii/
   *
   * 贪心算法。
   *
   * 假设我们现在在索引i的位置。
   *
   * 如果索引i的值为0，那么我们不可能再继续前进了，这种情况舍弃。
   *
   * 如果索引i的值不为0，那么我们下一步可以走到索引i + k(1 <= k <= nums[i])。
   * 而在索引i + k我们又可以走到索引i + k + p(1 <= p <= nums[i + k])，我们选取索引i + k的原则是i + k + p取得最大值。
   *
   * 对于贪心算法而言，其实现永远不是重点，其重点在于为什么可以使用贪心算法。那么，为什么本题可以这样使用贪心算法呢？
   *
   * （1）如果此时i + k + p的最大值仍然小于（数组的长度 - 1），说明经过此步还未能抵达数组中最后一个元素。
   *
   * 对于索引i而言，假设索引i下一步的最优解为索引i + k。索引i + k的下一步所能到达的范围是索引i + k + 1 ~ i + k + nums[i + k]。
   *
   * 假设索引i + k不是索引i下一步的最优解，索引i下一步的最优解为索引i + j(j != k)。
   * 索引i + j的下一步所能到达的范围是索引i + j + 1 ~ i + j + nums[i + j]，
   * 由索引i + k的定义可知，i + j + nums[i + j] <= i + k + nums[i + k]。
   *
   * 如果j >= k，那么i + j + 1 >= i + k + 1，索引i + j的下一步所能到达的范围是小于索引i + k所能到达的范围的，
   * 即如果索引i + j能到的地方，索引i + k也能到，但是索引i + k能到的地方，索引i + j却不一定能到。因此索引i下一步的最优解一定只可能是i + k。
   *
   * 如果j < k，对于索引i + k + 1及其之后的索引位置，索引i + j的下一步所能到达的范围是小于索引i + k所能到达的范围的，
   * 即如果索引i + j能到的地方，索引i + k也能到，但是索引i + k能到的地方，索引i + j却不一定能到。
   * 而对于索引i + k + 1之前的索引位置，索引i + k是到不了的，索引i + j能到，但是此时多走了一步路。
   * 因为我们最终肯定是要跨过索引i + k，我们本可以一步到达索引i + k的位置，下一步就跨过索引i + k了，
   * 现在我们第一步到达索引i + j的位置，下一步还不能保证跨过索引i + k。因此索引i下一步的最优解一定只可能是i + k。
   *
   * （2）如果此时i + k + p的最大值大于等于（数组的长度 - 1），说明经过此步能抵达数组中最后一个元素，显然索引i + k是最优解。
   *
   * 时间复杂度是O(n)，其中n为nums数组的长度。空间复杂度是O(1)。
   *
   * 执行用时：4ms，击败78.42%。消耗内存：42MB，击败68.36%。
   */
  public class Solution {
      public int jump(int[] nums) {
          int n = nums.length, steps = 0, now = 0;
          while (now < n - 1) {
              steps++;
              if (now + nums[now] >= n - 1) {
                  return steps;
              }
              int k = now + 1;
              for (int j = now + 1; j <= now + nums[now]; j++) {
                  if (j + nums[j] > k + nums[k]) {    //选取k的原则是i + k + nums[k]达到最大
                      k = j;
                  }
              }
              now = k;  //下一步是索引k
          }
          return steps;
      }
  }