今天解的題目是第四十五題 Jump Game II,題目給定一個整數陣列 nums,每個元素代表在該位置最多可以往前跳的步數,起始位置在索引 0,目標是找到到達最後一個索引所需的最少跳躍次數,並且題目保證一定可以到達終點。這題的核心思路是使用貪心法來追蹤當前能到達的範圍與最遠能延伸的範圍,我們定義 end 表示當前這一步能走到的最遠邊界,farthest 則用來記錄在這個範圍內能延伸到的最遠位置。遍歷陣列的過程中,每次更新 farthest = max(farthest, i + nums[i]),表示目前位置能夠跳到的最遠索引,當我們走到 end 的位置時,代表這一步的範圍已經結束,必須要再跳一次,於是將跳數加一並更新 end = farthest。如此不斷往前推進,直到最後一格,就能計算出最少的跳數。以範例 nums = [2,3,1,1,4] 為例,第一次從索引 0 跳出範圍能到達最遠索引 2,跳數加一,接著在範圍 [1,2] 中,利用 nums[1] = 3 可以延伸到索引 4,當走到索引 2 時再跳一次,更新 end = 4,剛好到達終點,因此答案是 2。