LeetCode-in-All
45. Jump Game II
Medium
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i]andi + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
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 <= 1040 <= nums[i] <= 1000- It’s guaranteed that you can reach
nums[n - 1].
Solution
func jump(nums []int) int {
length := 0
maxLength := 0
minJump := 0
for i := 0; i < len(nums)-1; i++ {
length--
maxLength--
maxLength = max(maxLength, nums[i])
if length <= 0 {
length = maxLength
minJump++
}
if length >= len(nums)-i-1 {
return minJump
}
}
return minJump
}
func max(a, b int) int {
if a > b {
return a
}
return b
}