Leetcode 45. Jump Game II

Leetcode Top Interview 150 的其中一題

題目描述

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each elementnums[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] and
• i + 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 <= 10^4
• 0 <= nums[i] <= 10000
• It’s guaranteed that you can reach nums[n - 1].

解法

思路：記錄從我們每一步可以到達的地方中，找出最遠下一步可以到哪 例如範例一 index 0 可以到 index 1, index 2

func jump(nums []int) int {
    res := 0 
    currFarest := 0
    start := 0

    for currFarest < len(nums)-1 {
        farest := 0

        for i := start; i <= currFarest; i++ {
            farest = max(farest, i + nums[i])
        }

        start = currFarest + 1 
        currFarest = farest

        res++
    }

    return res
}

func max(a, b int) int {
    if a > b { return a }
    return b
}

Time complexity : O(n^2) Space complexity : O(1)