目录
121.买卖股票最佳时机
题目描述
示例
算法分析
代码(python3)
122.买卖股票最佳时机II
题目描述
示例
算法分析
代码（python3）
55.跳跃游戏
题目描述
示例
算法分析
代码
45.跳跃游戏II
题目描述
示例
算法分析
代码
121.买卖股票最佳时机
题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
这个问题实际上是利用了“贪心算法”的思想。
算法分析
这个算法的目的是找出股票交易中的最大利润，即买入和卖出股票的最佳时机。算法的核心思想是：
- 维护一个最小值（mn）：这个变量用于记录遍历过的价格中的最小值。这相当于我们在寻找买入股票的最佳时机（即价格最低的时候）。
- 计算利润（ans）：对于每一个价格，我们计算如果在这个价格卖出股票，那么利润是多少（即当前价格减去之前记录的最小值）。然后，我们更新记录的最大利润（ans）。
为什么说是贪心算法？
- 局部最优选择：在每一步，我们都选择到目前为止看到的最小值作为可能的买入点，这是一个局部最优选择，因为我们假设在这一点上买入可以最大化后续可能的利润。
- 无回溯：一旦我们选择了某个点作为“可能的买入点”，我们就不会回头去改变这个选择（除非遇到一个更低的价格）。这符合贪心算法“一旦做出选择，不再更改”的特点。
代码(python3)
class Solution:def maxProfit(self, prices: List[int]) -> int:# mn用来记录前n个最小的值mn = prices[0]# ans用来记录前n个最小的值与当前值的差值的最大值ans = 0for x in prices:mn = min(mn,x)ans = max(ans,x-mn)return ans122.买卖股票最佳时机II
题目描述
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润
示例
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。
算法分析
遍历数组，如果当天买入第二天会涨，就在第二天卖出。否则当天就不买入。这个方法，最终利润是最大的。
代码（python3）
class Solution:def maxProfit(self, prices: List[int]) -> int:profit = 0for i in range(1, len(prices)):tmp = prices[i] - prices[i - 1]if tmp > 0:profit += tmpreturn profit55.跳跃游戏
题目描述
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
算法分析
遍历每一项,如果当前位置能到达并且大于前面所能到达的最大位置，就更新最大位置
代码
class Solution:def canJump(self, nums: List[int]) -> bool:# 遍历每一项max_i = 0for i,jump in enumerate(nums):# 如果当前位置能到达并且大于前面所能到达的最大位置，就更新最大位置if max_i>=i and i+jump>max_i:max_i = i+jumpreturn max_i>=len(nums)-145.跳跃游戏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]。
示例
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是2，从下标为 0 跳到下标为 1 的位置，跳 1步，然后跳3步到达数组的最后一个位置。
算法分析
想象有一条河，0和m一1分别是河的两岸。一开始，你在0，要到n-1。
把区间[i,i+nums[i]]视作一座桥。一开始只能建一座桥，也就是[0，nums[0]]。比如建造了一座从0到4的桥。
下一座桥要选哪个呢？
在可以选的桥中，选择右端点最大的桥。它会让你走的更远。
重复该过程，到达n-1时退出循环。修建的桥的数量就是答案。
代码
class Solution:def jump(self, nums: List[int]) -> int:ans = 0cur_right = 0 # 已建造的桥的右端点next_right = 0 # 下一座桥的右端点的最大值for i in range(len(nums) - 1):# 遍历的过程中，记录下一座桥的最远点next_right = max(next_right, i + nums[i])if i == cur_right: # 无路可走，必须建桥cur_right = next_right # 建桥后，最远可以到达 next_rightans += 1return ans
