package pers.vic.basics.leetcode;

/**
 * @description: 45. 跳跃游戏 II  {@literal https://leetcode-cn.com/problems/jump-game-ii/}  贪心算法
 * @author Vic.xu
 * @date: 2020/12/9 0009 8:48
 * @see J0055_M_CanJump
 */
public class J0045_H_Jump {
    /*
    给定一个非负整数数组，你最初位于数组的第一个位置。
    数组中的每个元素代表你在该位置可以跳跃的最大长度。
    你的目标是使用最少的跳跃次数到达数组的最后一个位置。
    说明:

    假设你总是可以到达数组的最后一个位置。
     */

    /**
     * 第一次尝试贪心算法
     * 贪心：局部算法中的最优解
     * 本题：
     * 1. 隐含条件：总是可以到达最后一个位置：省去了额外的判断
     * 2.在位置1时候，可以达到的最远距离是max = 1+nums[1]
     * 3.继续下一步在区间[2， max]中，找出能跳到的最大距离max2,当区间内的每一个位置都尝试完毕，则更新最远距离为max2，并且步数+1
     * 4. 重复上述步骤，在区间[max+1， max2]中找出能挑到的最大距离，直到最远距离大于等于数组
     */
    public static int jump(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        //需要的步数
        int step = 1;
        //总距离-目的下标
        int distance = nums.length - 1;
        //当前区域能达到的最远下标
        int curMax = nums[0];
        //已经到达的最远下标
        int max = curMax;
        //没有到终点 则继续往下走
        for (int i = 1; i < distance; i++) {
            if (max >= distance) {
                break;
            }
            curMax = Math.max(curMax, i + nums[i]);
            //如果当前区域结束，更新最远距离，且步骤+1
            if (i == max) {
                max = curMax;
                step++;
            }
        }
        return step;
    }

    public static void main(String[] args) {
        int[] nums = {7, 0, 9, 6, 9, 6, 1, 7, 9, 0, 1, 2, 9, 0, 3};
        //2
        System.out.println(jump(nums));

        int[] nums2 = {2, 3, 1, 1, 4, 2, 1, 2, 1, 2};
        //4
        System.out.println(jump(nums2));
        int[] nums3 = {1, 1, 1};
        //2
        System.out.println(jump(nums3));
    }

}