LeetCode Jump Game II：最少跳躍次數 — 貪心單次遍歷

題目描述

數組每個元素表示在該位置最多能向前跳躍的步數。已保證能到達終點，求到達最後一個下標的最少跳躍次數。

範例：

輸入: [2,3,1,1,4]
輸出: 2 (下標 0→1→4)

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

維護三個變量：

• steps：已跳躍次數。
• currentEnd：當前跳躍步數所能覆蓋的最遠邊界。
• farthest：在當前覆蓋範圍內，下一步能到達的最遠位置。

遍歷數組（不包括最後一個元素）：

1. 更新 farthest = max(farthest, i + nums[i])。
2. 當走到 i == currentEnd 時，必須再跳一步：steps++，並將 currentEnd = farthest。

這相當於在每一「層」的邊界處決定下一跳的最遠覆蓋。

參考代碼 (Python)

class Solution:
    def jump(self, nums):
        steps = 0
        current_end = 0
        farthest = 0
        for i in range(len(nums) - 1): # 不需處理最後位置
            farthest = max(farthest, i + nums[i])
            if i == current_end:
                steps += 1
                current_end = farthest
        return steps

複雜度分析

• 時間複雜度：O(n) —— 單次遍歷。
• 空間複雜度：O(1) —— 常數變量。