題目
#

題目簡述
#

給一個非負整數陣列 nums，你最初位於陣列的第一個位置。
陣列中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達最後一個位置。

範例
#

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: 從 index 0 跳躍 1 步到 index 1，然後跳躍 3 步到最後一個 index。

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: 無論如何你都會到達 index 3。它的最大跳躍長度是 0，這使得無法到達最後一個 index。

解題思路
#

這題要求我們判斷是否能夠從第一個位置跳躍到最後一個位置。我們可以使用貪心算法來解決這個問題，通過維護一個變數 maxReach 來記錄能夠到達的最遠位置。

解法
#

貪心

初始化 maxReach = 0，表示能夠到達的最遠位置
遍歷陣列中的每個位置 i
如果 i > maxReach，說明無法到達位置 i，返回 false
更新 maxReach = max(maxReach, i + nums[i])
如果能夠遍歷完整個陣列，返回 true

步驟
#

初始化變數：
- maxReach = 0：能夠到達的最遠位置
遍歷陣列：
- 檢查當前位置 i 是否能夠到達
- 如果 i > maxReach，返回 false
- 更新 maxReach = max(maxReach, i + nums[i])
返回結果：
- 如果能夠遍歷完整個陣列，返回 true

例子說明
#

nums = [2,3,1,1,4]

步驟	位置 i	跳躍長度 nums[i]	可到達位置 i+nums[i]	maxReach	是否可到達
初始化	-	-	-	0	-
i=0	0	2	0+2=2	2	0 ≤ 2 ✓
i=1	1	3	1+3=4	4	1 ≤ 2 ✓
i=2	2	1	2+1=3	4	2 ≤ 4 ✓
i=3	3	1	3+1=4	4	3 ≤ 4 ✓
i=4	4	4	4+4=8	8	4 ≤ 4 ✓

結果： true，可以到達最後一個位置

跳躍路徑： 0 → 1 → 4（跳躍 1 步到位置 1，再跳躍 3 步到位置 4）

完整程式碼
#

java

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;

        for (int i = 0; i < nums.length; i++) {
            // 如果當前位置無法到達，返回 false
            if (i > maxReach) {
                return false;
            }
            // 更新能夠到達的最遠位置
            maxReach = Math.max(maxReach, i + nums[i]);
        }

        return true;
    }
}