runtime 8 ms, beats 99.37% of cpp submissions
O(n) solution with explanation

tags: greedy

Jump Game II

📖 description

給定一個內容代表可以跳到下一格遠的陣列，求最少跳躍數。

ex.
    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.

🧠 solution

Jump Game
是 Jump Game 的變化題，不只是要輸出可不可以到達終點，而是要在假設可調達終點的情況下求出最少的跳躍數，在這個條件下我們如果仍然是由後往前看，最糟的時間複雜度為 O(n^2) ，因為每次遇到一個跳躍點都需要往後看一次，而如果是往前看，就可以節省重複看檢查的狀態，我們需要維護一個以當前的節點，最遠可以跳到哪裡的變數 ma ，使用 greedy 的方法，能跳到越遠的節點一定是一個當前最好的跳點，來累加總共需要的跳躍數。

⏳ time complexity

掃過一次陣列，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int jump(vector<int>& nums) {
        int ans = 0;
        int ma = 0;
        int now = 0;
        for(int i=0;i<nums.size()-1;i++){
            ma = max(ma,i+nums[i]);
            if(now == i){
                ans++;
                now = ma;
            }
        }
        return ans;
    }
};