1
2
3
4

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

1
2

输入: nums = [2,3,0,1,4]
输出: 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 贪心法
    /// 1. 依次遍历各个位置;
    /// 2. 记录每个位置时可到到达的最远位置next_max_pos;
    /// 3. 如果当前位置是上一次能跳到的最远位置,则跳到当前位置, 同时总跳的步数+1;
    pub fn jump(nums: Vec<i32>) -> i32 {
        let mut steps = 0; //已跳的步数
        let mut next_max_pos = 0; //下一步能跳到的最远位置
        let mut last_max_pos = 0; //上一次跳到的最远位置

        for pos in 0..nums.len() - 1 { //从起始位置开始一个一个条
            // 下一步可以跳到的最远的位置
            next_max_pos = next_max_pos.max(pos + nums[pos] as usize);
            // 如果可以从上一步跳最远距离到达当前位置
            if pos == last_max_pos {
                steps += 1; //跳一步
                //到达当前步能跳到的最远位置，则必须跳下一步
                last_max_pos = next_max_pos; //更新当前步最远能跳的位置
            }
        }

        steps as i32
    }
}
// @lc code=end