45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

1 2 3 4

>输入: nums = [2,3,1,1,4] >输出: 2 >解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1 2	>输入: nums = [2,3,0,1,4] >输出: 2

把该问题比喻为入职，数组下标是公司级别(入职门槛)，对应的值是公司级别之上的级别成长空间。你想用最少的跳槽次数入职最高级的公司

• 数组[2,3,1,2,4,2,3]

• 下标 0 1 2 3 4 5 6

最开始你没有工作，你的水平是2级，可以在2级及以下的公司里随便挑，此时候选公司有下标1和2

如果你想进入更高级别的公司，应该选择能够帮助你提升级别最多的公司。例如，公司1能够将你的级别提升到1+3=4级，而公司2只能提升到2+1=3级。显然，你应该选择公司1，然后升到4级。接下来，你可以跳槽到4级及以下的公司，每次都选择能够帮助你提升最多级别的公司，如此循环……直到水平级别足够入职梦中情司

只有每次跳槽都选择能够帮助你升级最多的公司，才能以最少的跳槽次数到达最高级别的公司

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution(object):
    def jump(self, nums):
        ans = 0; #跳槽次数
        curUnlock = 0; #当前你的水平能入职的最高公司级别
        maxUnlock = 0; #当前可选公司最多能帮你提到几级
        #从前向后遍历公司，最高级公司(nums.length-1)是目标，入职后不再跳槽，
        #所以不用看，故遍历范围是左闭右开区间[0,nums.length-1)
        for i in range(len(nums) - 1):
            #计算该公司最多能帮你提到几级(公司级别i+成长空间nums[i])，与之前的提级最高记录比较，打破记录则更新记录
            maxUnlock = max(maxUnlock, i + nums[i]) 
            print(maxUnlock)
            
            if (i == curUnlock): 
                # 把你当前水平级别能选的公司都看完了，你选择跳槽到记录中给你提级最多的公司，以解锁更高级公司的入职权限
                curUnlock = maxUnlock # 你跳槽到了该公司，你的水平级别被提升了
                ans+= 1 #这里记录你跳槽了一次
        return ans #返回跳槽总次数