LeetCode 筆記：跳躍遊戲 II - 最少跳躍次數的貪心策略

問題描述

給定非負整數陣列，初始位於第一個索引。每個元素代表該位置最大跳躍長度。目標是以最少跳躍次數到達最後一個索引。

範例：
A = [2,3,1,1,4] → 最少跳躍 2 次（索引 0→1，再 1→4）

解題思路：貪心 + 區間覆蓋

維護三個關鍵變數：

• last：上一跳能到達的最遠邊界
• curr：當前這一跳能到達的最遠邊界
• result：已執行的跳躍次數

遍歷陣列時，若索引超過 curr 則無法到達，返回 -1；當索引超過 last 時，必須執行下一跳，將 last 更新為 curr，次數加一；持續更新 curr = max(curr, i + A[i])。

C++ 實現

class Solution {
public:
    int jump(vector& nums) {
        int n = nums.size();
        if (n <= 1) return 0;
        
        int result = 0;      // 跳躍次數
        int last = 0;        // 上一跳最遠邊界
        int curr = 0;        // 當前跳最遠邊界
        
        for (int i = 0; i < n; ++i) {
            if (i > curr) return -1;              // 無法到達
            if (i > last) {                       // 需要下一跳
                last = curr;
                ++result;
            }
            curr = max(curr, i + nums[i]);        // 更新當前跳最遠
        }
        return result;
    }
};

圖解範例執行過程

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

相關延伸

此問題亦可用 BFS 解決（將每層視為一次跳躍），後續可嘗試驗證 BFS 寫法與貪心解的等價性。