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