贪心：跳跃游戏与最少步数

一、面试常考点

1. 可达性判断

维护当前最远可达位置 far。

2. 最少步数

按层推进：当前步能到的边界 end 与下一步最远 far。

二、细节介绍

1. Jump Game I

遍历时若 i > far 则不可达。

2. Jump Game II

每到 end 结算一步并更新边界。

三、示例代码

function jump(nums) {
  let steps = 0
  let end = 0
  let far = 0

  for (let i = 0; i < nums.length - 1; i++) {
    far = Math.max(far, i + nums[i])
    if (i === end) {
      steps++
      end = far
    }
  }

  return steps
}

四、常用应用场景

1. 分层覆盖问题

最少资源覆盖最大范围。

2. 网络传播跳数估算

在约束步数下覆盖节点。