45. 跳跃游戏 II

题意：

解题思路：

贪心: 本题是对下一步跳法的一种贪心算法，比如2，可以跳到3，1，但是3又能跳更远的距离，所以跳3
max: 当前路径能跳的最远距离 {2 3 1 1 4}:2能挑到1，但是路径中有3，所以最远距离max = 4
can_arrived:实际最远能跳的距离，能跳到的距离
0     1     2     3     4
2     3     1     1     4
$i = 0 max = 2 //当前能跳到下标为2的位置
$i = 1 step = 1 can_arrived = 2 max = 4
$i = 2 max = 4
$i = 3 step = 2 can_arrived = 4
$i = 4 max = 8

PHP代码实现：

class Solution {
    function jump($nums) {
        $step = 0;
        $can_arrived = 0;
        $max = 0;
        for ($i = 0; $i < count($nums); $i++) {
            if ($can_arrived < $i) {
                $step++;
                $can_arrived = $max;
            }
            $max = max($max, $i + $nums[$i]);
        }
        return $step;
    }
}

GO代码实现：

func jump(nums []int) int {
    step := 0
    can_arrived := 0
    maxPosition := 0
    for i := 0; i < len(nums); i++ {
        if can_arrived < i {
            step++
            can_arrived = maxPosition
        }
        maxPosition = max(maxPosition, i + nums[i])
    }
    return step
}
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}