題目網址：https://leetcode.cn/problems/jump-game-ii/

題意：給一非負整數 array nums, 你最初位於 nums 的第一個位置。

nums 中的每個元素代表你在該位置可以跳躍的最大長度。

假設你總是可以到達 nums 的最後一個位置。

返回到達 nums 的最後一個位置所需的最少的跳躍次數。

Solution：

想法：利用 Greedy, 用 [start, end] 來記錄每次跳躍的區間, 而 maxPos 則是用來紀錄 [start, end] 中所能跳躍的最遠 index。若 end ≥ nums.size() - 1 代表上一次跳躍已能抵達 nums 的終點, 因此結束循環

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0; // 所能跳躍的最遠 index
        int start = 0, end = 0, res = 0; // 起始區間 [start, end]

        while (end < nums.size() - 1) { // 只要 end ≥ nums 的最後一個 index 就終止
            // 計算下一次跳躍所能到的最遠 idx
            for (int i = start; i <= end; ++i) {
                maxPos = max(maxPos, i + nums[i]);
            }

            start = end + 1; // 下一次跳躍的起點
            end = maxPos; // 下一次跳躍的終點
            ++res;
        }
        
        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(1)$ ➔ 只需常數空間