0045. Jump Game I I

# 45. Jump Game II#

## 题目 #

Given an array of non-negative integers `nums`, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1:

``````Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
``````

Example 2:

``````Input: nums = [2,3,0,1,4]
Output: 2
``````

Constraints:

• `1 <= nums.length <= 1000`
• `0 <= nums[i] <= 10^5`

## 解题思路 #

• 要求找到最少跳跃次数，顺理成章的会想到用贪心算法解题。扫描步数数组，维护当前能够到达最大下标的位置，记为能到达的最远边界，如果扫描过程中到达了最远边界，更新边界并将跳跃次数 + 1。
• 扫描数组的时候，其实不需要扫描最后一个元素，因为在跳到最后一个元素之前，能到达的最远边界一定大于等于最后一个元素的位置，不然就跳不到最后一个元素，到达不了终点了；如果遍历到最后一个元素，说明边界正好为最后一个位置，最终跳跃次数直接 + 1 即可，也不需要访问最后一个元素。

## 代码 #

``````package leetcode

func jump(nums []int) int {
if len(nums) == 1 {
return 0
}
needChoose, canReach, step := 0, 0, 0
for i, x := range nums {
if i+x > canReach {
canReach = i + x
if canReach >= len(nums)-1 {
return step + 1
}
}
if i == needChoose {
needChoose = canReach
step++
}
}
return step
}
``````

Apr 8, 2023