runtime 69 ms, beats 93.58% of cpp submissions
O(n) solution with explanation

tags: greedy

Jump Game

📖 description

給定一個陣列 nums ，數值表示可以從該點往前跳多少格，回傳是否可以跳到最後一格。

ex.
    Input: 
        nums = [2,3,1,1,4]

    Output: true

    Explanation: 
        Jump 1 step from index 0 to 1, then 3 steps to the last index.

🧠 solution

使用 greedy 的想法，維護一個數字表示目前可以跳到最遠的位置 (能跳越遠表示能看的點越多)。

⏳ time complexity

遍歷一次陣列，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int r = 0;
        for(int i=0;i<nums.size();i++){
            if(r>=i){
                r = max(r,nums[i] + i);     // 維護目前能跳到最遠的位置
            }
            else{
                return false;
            }
        }
        return true;
    }
};