45. Jump Game II.md

45. Jump Game II

思路

跳格游戏，问最少跳多少步可跳到最后一个格子。

因为我们需要用最少的步数跳到最后一个格子，所以可以考虑用贪心的思想，不过这里贪婪并不是每次都要跳到最远的格子，而是贪婪地求出用一定步数所能跳出最远的范围，一旦当这个范围到达末尾时，此时所用的步数一定是最小步数。所以基本思想是假设我们求出了用step - 1步能跳到的最远格子，那么就可以求出用step能跳到的最远范围。

为此，先定义记录步数的变量step，再定义两个变量cur和pre分别来保存当前的能到达的最远位置和之前能到达的最远位置，然后从后往前遍历

• 如果当前位置i小于等于pre，说明还是在step步能到达的范围内，根据当前位置格子的值来更新cur:cur = max(cur, i + nums[i])；
• 如果当前位置i等于了pre，说明到达了step步能到达的范围内的最后一个格子，所以此时我们需要更新pre为cur，然后将step加1。

时间复杂度O(n)，空间复杂度O(1)

C++

写法一

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), i = 0, cur = 0, pre = 0, step = 0;
        for(int i = 0; i < n - 1; i++){
            cur = max(cur, i + nums[i]);
            if(i == pre){
                pre = cur;
                step++;
                if(cur >= n - 1) return step;
            }
        }
        return step;
    }
};

写法二

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), i = 0, cur = 0, pre = 0, step = 0;
        while(cur < n - 1){
            while(cur < n - 1 && i <= pre)
                cur = max(cur, i + nums[i++]);
            pre = cur;
            step++;
        }
        return step;
    }
};