leetcode45. 跳跃游戏 II 吴丹阳

题目

45. 跳跃游戏 II

解法

1. 遍历的同时记录 stepCnt
2. 只有在第一个 max 遍历完之后，才可以增加 stepCnt

class Solution {
    
    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function jump($nums) {
        if (empty($nums)) {
            return 0;
        }
        
        if (count($nums) == 1) {
            return 0;
        }
        
        $max      = $nums[0];
        $stepCnt  = 0;
        $preIndex = 1;
        $len      = count($nums);
        while (true) {
            $size = $max;
            $stepCnt++;
            for ($i = $preIndex; $i <= $size; $i++) {
                if ($i == $len-1) {
                    return $stepCnt;
                }
                $max = max($nums[$i] + $i, $max);
            }
        }
        
    }
}

[[leetcode-55. 跳跃游戏]]

参考