55. Jump Game

Medium

Description

給定一個非負整數陣列 nums，每個元素代表在該位置最多能跳的步數。從第一個位置出發，判斷能否到達最後一個位置。

Example:

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

Intuition#

維護「能到達的最遠位置」，遍歷時若當前位置超過最遠位置則無法到達。

從左到右掃描，維護目前能到達的最遠索引 maxReach
若 i > maxReach，代表當前位置不可達，回傳 false
否則更新 maxReach = max(maxReach, i + nums[i])

Approaches#

1: DP（自底向上）#

概念: dp[i] 記錄位置 i 是否可達，對每個可達位置更新它能跳到的所有位置。
時間複雜度: O(n^2) 最差情況
空間複雜度: O(n)

class Solution {
    fun canJump(nums: IntArray): Boolean {
        val n = nums.size
        val dp = BooleanArray(n)
        dp[0] = true
        for (i in 1 until n) {
            for (j in i - 1 downTo 0) {
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true
                    break
                }
            }
        }
        return dp[n - 1]
    }
}

⭐2: Greedy（最遠可達位置）#

概念: 維護一個變數 maxReach 記錄目前能到達的最遠位置，線性掃描即可。
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun canJump(nums: IntArray): Boolean {
        var maxReach = 0
        for (i in nums.indices) {
            if (i > maxReach) return false
            maxReach = maxOf(maxReach, i + nums[i])
        }
        return true
    }
}

🔑 Takeaways#

Pattern: 最遠可達位置 — 貪心維護一個邊界值
關鍵技巧: 很多「能否到達」的問題都可以用貪心維護邊界來解，不需要完整的 DP 表格