LeetCode.45.跳跃游戏 II（中等）

题目

LeetCode.45.跳跃游戏 II（中等）

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。

题解

模拟

不知道怎么办，先模拟一遍跳跃过程。
假设nums[0]是3，那么可以选择跳到1、2、3的位置。
假设nums[1]是1、nums[2]是10、nums[3]是3，那么肯定选择先跳到2的位置，再跳10个长度，这样跳跃次数最少。
后面再跳跃还是重复这个同样的选择过程。

归纳

可以得知下一步的跳跃选择，应该在当前可以跳跃到的范围内找一个最远的长度来跳。就是贪心选择，从局部最优得出全局最优。

怎么找最远可以跳跃的长度？

只有一个个遍历数组，漏一个都不行

什么时候计数跳跃次数？

因为会在可以跳跃到的范围内找到一个最远的长度来跳，也就是说这个范围内只会跳一次。那就顺便在遍历数组的时候等到达了跳跃范围的边界就可以计数跳跃次数了。

class Solution {
    fun jump(nums: IntArray): Int {
        val n = nums.size
        var count = 0
        var end = 0
        var maxNext = 0
        for (i in 0 until n - 1) {
            maxNext = maxOf(maxNext, nums[i] + i)
            if (i == end) {
                end = maxNext
                count++
            }
        }
        return count
    }
}