[LeetCode] 45. 跳跃游戏 II（java实现）贪心

1. 题目2. 读题（需要重点注意的东西）3. 解法4. 可能有帮助的前置习题5. 所用到的数据结构与算法思想6. 总结

思路（贪心）：
计算机一秒能处理8*10⁷的数据，此题nums最大长度为10⁴，因此如果是时间复杂度O(n²)的算法，一定会超时。
因此主要思路是： 遍历当前区间，从每一段区间中找最大的值作为下个区间的终点，每走完一个区间，跳跃步长加1，直到遍历完整个数组。

---------------------------------------------------解法---------------------------------------------------：

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int max = 0; // 记录下个区间的最大值在哪
        int step = 0; // 记录走了几个区间（即跳了多少步）
        int end = 0; // 记录当前区间的终点
        for(int i = 0;i < n - 1;i++){
            // 找这段区间内的最大值
            max = Math.max(max,i + nums[i]);
            // 走到了这段区间的终点，更新下一段区间的最大值为end，走完一个区间了，step++
            if(i == end){
                end = max;
                step++;
            }
        }
        return step;
    }
}

可能存在的问题：

贪心 6. 总结

贪心的特点：能从局部最优解得到全局最优解