【leetcode】跳跃游戏 (贪心)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 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

思路分析：

其实一开始看这道题就预感是贪心了。
数组中的每个元素代表你在该位置可以跳跃的最大长度，意味着你可跳跃的点是一个区间[cur,cur+nums[cur]. 我们可以考虑每走一步，就更新这个区间。这就是从局部最优解推向全局最优解。
因此，定义一个Max表示当前跳的所有点中能跳到最远的点。如果当前的点cur > Max 就意味着超界了，return false. 如果能够走完所有的点或者当Max >= n-1就可以直接return true.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int Max = 0, n = nums.size();
        for(int i = 0;i < n;i++)    //Max表示前面走的所有位置中能跳的最远的位置
        {
            if(i > Max) return false;   //如果走的位置>Max，表示不合法
            Max = max(Max,i+nums[i]);   //每走一个位置，更新一次Max
        }
        return true;
    }
};