day32| 122+55+45

122. 买卖股票的最佳时机

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

思路：

1. 可以当天买当天买

2. 也可以第i-1买，第i天卖，甚至第i天再买

3. 如果说后一天的售价比前一天高，是否就可以一直执行前一天买，后一天卖的操作

4. 利用一个判断语句，如果前天买，后天卖的收益为正，就加入总收益

5. 遍历得最大收益值

代码如下：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            tmp = prices[i] - prices[i - 1]
            if tmp > 0: profit += tmp
        return profit

55. 跳跃游戏

题目简述：

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

思路：

1. 能到达较远的位置，那么一定能到达较近的位置

2. 直接遍历数组，如果当前位置能到达，并且当前位置+跳数>最远位置，不断更新能够到达的最远位置即可

3. 如果最远位置超过了最后一个位置的下标，即可返回True

代码如下：

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        max_i = 0       #初始化当前能到达最远的位置
        for i, jump in enumerate(nums):   #i为当前位置，jump是当前位置的跳数
            if max_i>=i and i+jump>max_i:  #如果当前位置能到达，并且当前位置+跳数>最远位置  
                max_i = i+jump  #更新最远能到达位置
        return max_i>=i

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. 每次利用一个范围的元素中，确定下一个范围

2. 利用上一个范围内的数字，确定下一定范围的边界

3. 每次遍历到end，即进行step+1的操作

4. 之所以如此，从一个范围到另一个范围，是可以通过一步就到达的

比如数组[2,3,1,1,4]，下标分别为[0,1,2,3,4]

1. 从左向右遍历，0下标的元素必定是要经过的

2. 得到第0个下标对应的2，确定了一个最初的边界，也即一个小数组[3,1]，对应下标为1，2

3. 继续从左向右遍历，取得 元素3，发现 3+index(3)=3+1>index(2)=2，更新范围，知道了下一个范围的右边界是下标4对应的那个位置，左边界是上一个end+1，都是闭区间

4. 继续从左向右遍历，取得 元素1，发现1 +index(2)=1+2<4，没用，不更新边界

5. 当时此时元素1对应的下标为 我们由元素2 确定的右边界，再往后就要step加1了

6. 以此类推

代码如下：

class Solution:
    def jump(self, nums: List[int]) -> int:
        # 能跳到远的点，就肯定能跳到近的点
        # 每次在上次能跳到的范围（end）内选择一个能跳的最远的位置作为下次的起跳点！
        # 走到end也更新end为上一范围点能跳到的最远位置
        n = len(nums)
        maxPos, end, step = 0, 0, 0
        for i in range(n - 1):
            if maxPos >= i:
                maxPos = max(maxPos, i + nums[i])
                if i == end:
                    end = maxPos
                    step += 1
        return step