題目描述:給定陣列 nums,nums[i] 表示在位置 i 最多能跳多遠,判斷是否能從索引 0 到達最後一個索引。
解題思路:貪心法:維護一個變數 maxReach 表示目前能到達的最遠位置。遍歷陣列,若當前位置 i > maxReach,說明無法到達位置 i(被困住了),回傳 false。否則更新 maxReach = max(maxReach, i + nums[i])。若遍歷完成,說明可以到達終點。
時間複雜度:O(n) — 單次線性掃描。
空間複雜度:O(1) — 只用一個變數。
1. Set maxReach = 0 2. For i from 0 to n-1: a. If i > maxReach: return false b. maxReach = max(maxReach, i + nums[i]) 3. Return true
遞迴無記憶 O(2^n) 最壞:嘗試所有跳躍組合,重複計算。
貪心不同方向 O(n):從右往左追蹤最左能到達位置,改為掃描所有位置並記錄最遠可達 — 邏輯相反但複雜度相同。