45. Jump Game II - Medium

前往題目

想法

• 從後往前，但不知道怎麼判斷最小跳幾次

思路

這種題目無非就是窮舉，優化就是記憶法，但是這題只需要判斷哪個選擇最有潛力，也就是貪心思想

1. 從前往後
2. 每次紀錄最遠可以跳到哪
3. 如果來到剛剛著陸的地方就再跳一次，跳到目前最遠的位置

Code

class Solution {
    public int jump(int[] nums) {
        int farthest = 0; // 目前最遠距離
        int jump = 0; // 跳了幾次
        int end = 0; // 目前跳到的位置
        
        // 最後一位要skip，因為是終點，否則會再跳一次
        for (int i = 0; i < nums.length - 1; ++i) {
            // 最遠可以到哪裡
            farthest = Math.max(nums[i] + i, farthest);

            // 如果已經到了剛剛跳過來的位置
            if (end == i) {
                // 再跳一次
                ++jump;
                // 跳到目前可跳的最遠位置
                end = farthest;
            }
        }
        return jump;
    }
}