給定一個非負整數陣列
nums，每個元素代表在該位置最多能跳的步數。從第一個位置出發，判斷能否到達最後一個位置。
Example:
Input: nums = [2,3,1,1,4] Output: true
Intuition
TIP
維護「能到達的最遠位置」，遍歷時若當前位置超過最遠位置則無法到達。
- 從左到右掃描，維護目前能到達的最遠索引
maxReach - 若
i > maxReach，代表當前位置不可達，回傳 false - 否則更新
maxReach = max(maxReach, i + nums[i])
Approaches
1. DP (bottom-up) — O(n^2) / O(n)
- Idea:
dp[i]記錄位置 i 是否可達，對每個可達位置更新它能跳到的所有位置。 - Time:
O(n^2)最差情況 - Space:
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 (farthest reach) — O(n) / O(1)
- Idea: 維護一個變數
maxReach記錄目前能到達的最遠位置，線性掃描即可。 - Time:
O(n) - Space:
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: 最遠可達位置 — 貪心維護一個邊界值
- Key trick: 很多「能否到達」的問題都可以用貪心維護邊界來解，不需要完整的 DP 表格