今天做了一道题，用了O(n)O(1)解决的，觉得比官方写的题解的O(n)解法来的直观，记录下

题目：45. 跳跃游戏II

贪心正向跳跃的基本思路是：

1.到达位置i，从i处可以到达的位置j的范围是 i<=j<=i+nums[i]

2.选择最优位置的策略是：贪心选择能到达最远点的位置

class Solution {
  
    public int jump(int[] nums) {
        int cou = 0;
        int index = 0;
        while(index < nums.length-1){
            int max = -0x3f;
            int selectj = 0;//一次跳跃要选择的位置
            for(int i=0;i<=nums[index];i++){ //遍历一次跳跃要选择的位置
                int j = index+i; //从每个候选位置出发可以到达的最远下标
                if(j >= nums.length-1){ //如果已经可以到达终点不需要再考虑其他位置
                    selectj = nums.length-1;
                    break;
                }
                if( j+nums[j]>max){ //更新最佳选择
                    max = j+nums[j];
                    selectj = j;
                }
            }
            index = selectj;
            cou++;
        }
        return cou;
    }
}

虽然有两层循环，但时间复杂度是O(n)，因为对每个位置，我们只需要计算与判断一次，空间也是O(1)