Problem :

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1 :

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2 :

Input: nums = [2,3,0,1,4]
Output: 2

核心思維 :

1. 獲取陣列大小並設置記錄跳躍的次數、當前能達到的最遠位置和當前跳躍的邊界
2. 將陣列遍歷至倒數第二個位置，並更新能達到的最遠位置
3. 若能達到當前跳躍的範圍邊界，則增加跳躍次數並更新當前跳躍範圍的邊界
4. 回傳最小的跳躍次數

程式碼 :

class Solution {
public:
    int jump(vector<int>& nums) {
        //獲取陣列大小
        int n = nums.size();
        //紀錄跳躍的次數
        int jumps = 0;
        //紀錄當前能達到的最遠位置
        int maxPos = 0;
        //紀錄當前跳躍的邊界
        int currReach = 0;
        //將陣列遍歷至倒數第二個位置
        for(int i = 0; i < n-1; i++){
            //更新能達到的最遠位置
            maxPos = max(maxPos, i + nums[i]);
            //若能達到當前跳躍範圍的邊界
            if(i == currReach){
                //增加跳躍次數
                jumps++;
                //更新當前跳躍範圍的邊界
                currReach = maxPos;
            }
        }
        //回傳嘴小的跳躍次數
        return jumps;
    }
};

結論 :

這題的目標是找出陣列的起始位置到最後一個位置所需的最小跳躍次數，透過遍歷陣列及使用maxPos 和 currReach 兩個指標來追蹤當前能達到的最遠位置和跳躍範圍，這段程式碼的時間複雜度O(n)。