LeetCode 55. 跳躍遊戲：

55. 跳躍遊戲

給定一個非負整數數組，你最初位于數組的第一個位置。

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

判斷你是否能夠到達最後一個位置。

示例 1:

輸入: [2,3,1,1,4]

輸出: true

解釋: 我們可以先跳 1 步，從位置 0 到達 位置 1, 然後再從位置 1 跳 3 步到達最後一個位置。

示例 2:

輸入: [3,2,1,0,4]

輸出: false

解釋: 無論怎樣，你總會到達索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 是以你永遠不可能到達最後一個位置。

連結：https://leetcode-cn.com/problems/jump-game 

思路：參考 力扣題解 

（1）如果某一個作為 起跳點 的格子可以跳躍的距離是 3，那麼表示後面 3 個格子都可以作為 起跳點。

（2）可以對每一個能作為 起跳點 的格子都嘗試跳一次，把 能跳到最遠的距離 不斷更新。

（3）如果可以一直跳到最後，就成功了。

時間複雜度：O(n)

空間複雜度：O(1)

bool canJump(vector<int>& nums) {
    int k = 0;  // 每次保留周遊過的元素中最遠位置，若最遠位置大于末尾元素所在位置，則可到達傳回true
    for (int i = 0; i < nums.size(); i++)
    {
        if (i > k)
            return false;
        k = max(k, i + nums[i]);    // 目前能到達的最遠位置 (i + nums[i])為: (目前位置i + 目前最遠能跳到的步數nums[i])，然後與之前能到達的最遠位置k比較，保留較大的一個
    }
    return true;
}