leetcode-jump-game-ii

题目大意

　　https://leetcode.com/problems/jump-game-ii/

　　接续https://leetcode.com/problems/jump-game/，求从数组起点跳到终点的最小步

题目分析

　　本题不要直接使用基于队列的暴力BFS，因为并不需要枚举出所有路径，但也是基于BFS的思想，从起点开始，类似与层次遍历，每次遍历一层获得下一层的有边界，然后继续遍历下一层。讨论区中还有更为精简的代码：

https://discuss.leetcode.com/topic/11408/single-loop-simple-java-solution/4

代码

public class Solution {
    // BFS
    public int jump(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        if(len == 1) {
            return 0;
        }
        int start = 0;
        int end = 0;
        int level = 0;
        while (start <= end) { // 每一层的左右闭区间的边界index
            int maxJump = -1;
            level++;
            for (int i = start; i <= end; i++) {
                if (nums[i] + i >= len - 1) { // 已经能到达末尾直接返回
                    return level;
                }
                maxJump = Math.max(nums[i] + i, maxJump);
            }
            if (maxJump <= end) { // 永远也到达不了末尾，直接返回INT_MAX
                return Integer.MAX_VALUE;
            }
            start = end + 1;
            end = maxJump;
        }
        return Integer.MAX_VALUE;
    }
}

　　时间复杂度 O(n)