題目描述:給定一個非負整數陣列 nums,初始位置在索引 0,nums[i] 表示在第 i 格最多能往前跳幾步。保證一定能到達最後一格,求到達最後一格的最少跳躍次數。
解題思路:
採用貪心 BFS 分層的思路,類似 BFS 的「層」概念:每一跳代表一層,每一層包含用相同跳躍次數能到達的所有位置。
關鍵觀察:
[l, r](代表「本層」的範圍)farthest[r+1, farthest],跳躍次數加 1關鍵細節:
r >= n-1(最後一格已在視窗內),直接返回當前跳躍次數,無需再跳n-2(不需要從最後一格再跳出去)為何貪心正確?每次我們選擇最遠可達位置,等同於 BFS 中一次性展開整層節點,確保在最少跳躍次數下抵達終點。
時間複雜度:O(n) — 雖然寫作雙層迴圈形式,但內層迴圈的指標 l 只會單調遞增,每個索引只會被遍歷一次,整體為 O(n)。
空間複雜度:O(1) — 只使用常數個輔助變數(jumps、l、r、farthest),無需額外資料結構。
1. If n == 1, return 0 (already at destination)
2. Initialize jumps=0, l=0, r=0, farthest=0
3. While r < n-1 (haven't reached last index yet):
a. For each position i in [l, r]:
farthest = max(farthest, i + nums[i])
b. l = r + 1 (advance window start)
c. r = farthest (advance window end to farthest reachable)
d. jumps += 1
4. Return jumps動態規劃 O(n²):定義 dp[i] 為到達第 i 格的最少跳躍次數。對每個 i,枚舉所有能跳到 i 的位置 j(即 j + nums[j] >= i),dp[i] = min(dp[j] + 1)。正確但時間複雜度為 O(n²),不如貪心高效。
貪心精簡版(單指標)O(n):不維護視窗 [l, r],僅用 curEnd(當前跳躍層的右端)和 farthest(可達最遠),當 i == curEnd 時跳躍次數加一並更新 curEnd = farthest。與視窗版本等價,但程式碼更簡潔,只需一層迴圈。
nums[i] 可以是負數(即某些格子強制向後退),問題是否仍有貪心解,還是必須改用 DP?cost[i],如何求到達終點的最小總代價?