45. Jump Game II

1.問題

• 需要花幾步才能到達最後一格

2.想法

• 提問

• function header, parameter

• test input

• 說明想法

  • 當"當前的索引"大於"上一次所能到達的最遠索引時", 將計數器+1, 並且將"上一次所能到達的最遠索引"更新為"當前所能到達的最遠索引"

  • 每走一步都更新"當前所能到達的最遠索引"

• 測試計算複雜度

3.程式碼

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0 ;
        }
        
        int res = 0, last = 0, curr = 0;
        
        for (int i = 0; i < n; i++) {
            if (i > last) {
                last = curr;
                res++;
            }   
            curr = max(curr, i + nums[i]);
        }
        
        return res;
    }
};