45. Jump Game II

Medium
Description

給定一個非負整數陣列 nums，每個元素代表在該位置最多能跳的步數。從索引 0 出發，保證一定能到達最後一個位置。求到達最後一個位置的最少跳躍次數。

Example:

Input: nums = [2,3,1,1,4] Output: 2 (跳到索引 1，再跳到最後)

Intuition#

BFS 思維：每一「跳」相當於一層，在當前層能到達的所有位置中找下一層的最遠邊界。

  • 把問題想成 BFS：第 0 層是起點，第 1 層是從起點一跳能到的所有位置…
  • 維護當前層的邊界 end 和下一層能到的最遠位置 farthest
  • 每次 i 到達 end 時，跳躍次數 +1，更新 end = farthest

Approaches#

1: DP#

  • 概念: dp[i] 代表到達位置 i 的最少跳躍次數，對每個位置更新它能跳到的位置。
  • 時間複雜度: O(n^2) 最差情況
  • 空間複雜度: O(n)
class Solution {
    fun jump(nums: IntArray): Int {
        val n = nums.size
        val dp = IntArray(n) { Int.MAX_VALUE }
        dp[0] = 0
        for (i in 0 until n) {
            for (j in 1..nums[i]) {
                if (i + j < n) {
                    dp[i + j] = minOf(dp[i + j], dp[i] + 1)
                }
            }
        }
        return dp[n - 1]
    }
}

⭐2: Greedy（BFS 分層）#

  • 概念: 維護當前跳躍範圍的邊界，到達邊界時跳躍次數 +1 並擴展到下一範圍。
  • 時間複雜度: O(n)
  • 空間複雜度: O(1)
class Solution {
    fun jump(nums: IntArray): Int {
        var jumps = 0
        var end = 0
        var farthest = 0
        for (i in 0 until nums.size - 1) {
            farthest = maxOf(farthest, i + nums[i])
            if (i == end) {
                jumps++
                end = farthest
            }
        }
        return jumps
    }
}

🔑 Takeaways#

  • Pattern: BFS 分層遍歷 — 用邊界變數模擬 BFS 的層次
  • 關鍵技巧: 迴圈只到 nums.size - 2（不含最後一個），避免在終點處多算一跳；這種「隱式 BFS」技巧也適用於其他最短路徑問題
Backward Greedy 53. Maximum Subarray Forward