Problem: 55. 跳躍游戲
給你一個非負整數數組 nums ，你最初位于數組的 第一個下標 。數組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達最后一個下標，如果可以，返回 true ；否則，返回 false 。

整體思路

這段代碼旨在解決經典的 “跳躍游戲” (Jump Game) 問題。問題要求判斷給定一個非負整數數組，你是否能夠從第一個索引（位置0）開始，最終到達數組的最后一個索引。數組中的每個元素代表你在該位置可以跳躍的最大長度。

該算法采用了一種非常高效且直觀的 貪心算法 (Greedy Algorithm)。其核心思想不是去模擬每一步具體的跳躍，而是去維護一個當前可到達的最遠距離。

算法的邏輯步驟如下：

1. 維護一個“可達范圍”：

   • 算法使用一個變量 maxLoc 來記錄從起點（索引0）出發，通過已經訪問過的所有位置，能夠到達的最遠索引。
   • maxLoc 初始化為 0，因為我們最初就站在索引 0 的位置。

2. 遍歷與檢查：

   • 算法通過一個 for 循環，從左到右遍歷數組的每一個位置 i。
   • 核心檢查（可達性判斷）：在循環的每一步，首先檢查當前位置 i 是否在之前計算出的 maxLoc 的覆蓋范圍之內。即 if (i > maxLoc)。
     • 如果 i > maxLoc，這意味著當前位置 i 根本無法從任何前面的位置跳躍到達。就好像河流中間斷了一截，我們永遠也到不了對岸。在這種情況下，我們不可能到達數組的末尾，因此直接返回 false。
   • 貪心更新（擴展范圍）：如果當前位置 i 是可達的，我們就利用這個位置的跳躍能力來嘗試擴展我們的“可達范圍”。
     • 從位置 i 出發，最遠可以跳到 i + nums[i]。
     • 我們將這個新的可達距離與已知的最遠距離 maxLoc 進行比較，并更新 maxLoc 為兩者中的較大值。即 maxLoc = Math.max(maxLoc, i + nums[i])。
     • 這個貪心的選擇在于，我們總是希望把我們能到達的邊界推得盡可能遠。

3. 最終結果：

   • 如果循環能夠順利完成（即從未觸發 i > maxLoc 的條件），這意味著數組的每一個位置（包括最后一個位置 n-1）都在我們的可達范圍之內。
   • 因此，只要循環能走完，就說明最后一個位置是可達的，返回 true。

完整代碼

class Solution {/*** 判斷是否能從數組的第一個位置跳到最后一個位置。* @param nums 數組，每個元素代表在該位置的最大跳躍長度。* @return 如果可以到達最后一個位置，則返回 true，否則返回 false。*/public boolean canJump(int[] nums) {int n = nums.length;// maxLoc: 記錄從起點出發，當前能夠到達的最遠位置的索引。// 這是一個貪心選擇，我們總是希望這個值越大越好。int maxLoc = 0;// 遍歷數組的每一個位置，i 代表當前位置的索引。for (int i = 0; i < n; i++) {// 核心判斷：檢查當前位置 i 是否可達。// 如果當前位置 i 已經超出了之前所有位置能夠到達的最遠距離 maxLoc，// 說明 i 這個位置是無論如何也無法到達的，因此直接返回 false。if (i > maxLoc) {return false;}// 貪心更新：更新能夠到達的最遠位置。// 從當前位置 i 出發，最遠可以跳到 i + nums[i]。// 我們取這個新值與已知的最遠位置 maxLoc 中的較大者，作為新的最遠可達距離。maxLoc = Math.max(maxLoc, i + nums[i]);// 一個小優化：如果 maxLoc 已經能覆蓋或超過最后一個位置，就可以提前結束了。// if (maxLoc >= n - 1) {//     return true;// }}// 如果循環能夠順利完成，意味著數組的最后一個位置（n-1）也是可達的// (因為它沒有在 if (i > maxLoc) 中被攔截)，因此返回 true。return true;}
}

時空復雜度

時間復雜度：O(N)

1. 循環：算法的核心是一個 for 循環，它從 i = 0 遍歷到 n-1。這個循環最多執行 N 次，其中 N 是 nums 數組的長度。
2. 循環內部操作：
   • 在循環的每一次迭代中，執行的都是基本的比較、加法和 Math.max 操作。
   • 這些操作的時間復雜度都是 O(1)。

綜合分析：
算法由 N 次 O(1) 的操作組成。因此，總的時間復雜度是 N * O(1) = O(N)。

空間復雜度：O(1)

1. 主要存儲開銷：算法只使用了幾個固定數量的整型變量（n, maxLoc, i）。
2. 空間大小：這些變量的數量不隨輸入數組 nums 的大小 N 而改變。

綜合分析：
算法沒有使用任何與輸入規模 N 成比例的額外數據結構（如新數組或哈希表）。因此，其額外輔助空間復雜度為 O(1)。

參考靈神