如何申请网站com域名,wordpress onethink,建立一个同城网站要怎么做,设计师联盟室内效果图121. 买卖股票的最佳时机
一、题目难度
简单
三、题目描述
给定一个数组 prices#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票#xff0c;并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获…121. 买卖股票的最佳时机
一、题目难度
简单
三、题目描述
给定一个数组 prices它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0。
四、示例
示例1
输入[7,1,5,3,6,4] 输出5 解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6 - 1 5。 注意利润不能是 7 - 1 6因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。
示例2
输入prices [7,6,4,3,1] 输出0 解释在这种情况下没有交易完成所以最大利润为 0。
五、提示
1 prices.length 1050 prices[i] 104
六、贪心算法求解思路
一整体思路
我们的目标是通过一次买入和一次卖出操作来获取最大利润。贪心算法的思路就是在遍历股票价格数组的过程中始终记录当前已经出现过的最低买入价格然后用当前价格减去这个最低买入价格得到当前可能的最大利润不断更新这个最大利润值直到遍历完整个数组。
二贪心思路
贪心算法一般步骤的分析
1. 将问题分解为若干个子问题
分析 在本题中可以将整个股票交易过程按每一天来看作一个子问题。每一天我们都面临一个决策是否更新最低买入价格以及基于当前价格和最低买入价格计算可能的最大利润。通过依次处理每一天的情况最终汇总得到整个交易周期内的最大利润所以整个问题可以分解为按天来考虑的一系列子问题。初始化变量 设 min_price 为一个较大的值可以初始化为 prices[0]因为后续会不断更新它为更小的值它用来记录到目前为止出现过的最低买入价格。设 max_profit 为 0它用来记录到目前为止能获取到的最大利润。
2. 找出适合的贪心策略
分析 贪心策略就是在遍历股票价格数组的过程中始终保持记录到当前为止所出现过的最低买入价格。因为我们希望买入价格尽可能低这样在后续任何一天卖出时才有可能获得最大的利润。所以每到一天就比较当天的股票价格和已记录的最低买入价格如果当天价格更低就更新最低买入价格这就是我们确定的贪心策略。
3. 求解每一个子问题的最优解
分析 对于每一天这个子问题其最优解就是基于当前已经确定的最低买入价格通过前面的贪心策略不断更新得到计算当天卖出能获得的最大利润。即通过当天的股票价格减去最低买入价格得到一个差值如果这个差值大于之前记录的最大利润就更新最大利润值。遍历数组 从数组的第二个元素索引为 1开始遍历 prices 数组因为第一个元素已经作为初始的 min_price 考虑过了。对于每个元素 prices[i] 首先更新 min_price比较当前元素 prices[i] 和 min_price如果 prices[i] 小于 min_price则将 min_price 更新为 prices[i]。这一步是为了始终记录到目前为止出现过的最低买入价格。然后更新 max_profit计算当前价格 prices[i] 减去 min_price 的差值得到当前可能的最大利润将这个差值与 max_profit 进行比较如果差值大于 max_profit则将 max_profit 更新为这个差值。这一步是为了不断更新能获取到的最大利润值。
4. 将局部最优解堆叠成全局最优解
分析 在遍历完整个数组后最后记录下来的最大利润值就是全局最优解。因为在每一天我们都通过贪心策略找到了当天基于最低买入价格能获得的最大利润局部最优解随着遍历的进行不断更新这个最大利润值最终这个值就代表了在整个交易周期内能够获得的最大利润也就是将每一天的局部最优解堆叠起来形成了全局最优解。返回结果 遍历完整个数组后max_profit 中存储的就是通过一次买入和一次卖出操作所能获取到的最大利润直接返回 max_profit 即可。
代码对应解释
def maxProfit(prices):if not prices:return 0min_price prices[0] # 初始化最低买入价格为第一天的价格max_profit 0 # 初始化最大利润为0# 以下循环对应处理每一天的子问题for price in prices[1:]:# 对应找出适合的贪心策略步骤更新最低买入价格if price min_price:min_price priceprofit price - min_price # 计算当天基于当前最低买入价格的利润# 对应求解每一个子问题的最优解步骤更新最大利润if profit max_profit:max_profit profitreturn max_profitclass Solution:def maxProfit(self, prices: List[int]) - int:# 特殊情况空集if not prices:return 0# 正常情况初始化min_price prices[0] # 初始化当前最低买入价格为prices[0]max_profit 0 # 初始化最大利润为0 # 从索引1实际2开始循环遍历股票数组直接遍历price值# 循环处理每一天的子问题for price in prices[1:]:# 更新当前min_price min(price, min_price)cur_profit price - min_pricemax_profit max(max_profit, cur_profit)return max_profit在上述代码中
首先判断输入的数组是否为空如果为空则返回 0。接着初始化 min_price 和 max_profit。然后通过循环遍历数组在循环中不断更新 min_price 和 max_profit。最后返回 max_profit它就是所能获取到的最大利润。
动态规划解法
思路通过定义状态与状态转移方程解决问题 dp[i]定义为第i天卖出股票所能获得的利润dp[i] max(dp[i - 1], prices[i] - min_price)是状态方程其中min_price是第i天之前包括第i天的最低股票购入价格 代码步骤 特解空集初始化 收入数组dp一维dp[i]长len(prices)所有值为0最低买入价格min_price prices[0] 循环遍历数组:(从第二天索引1开始) 首先更新最低买入价格dp[i] max(dp[i - 1], prices[i] - min_price返回最后一个dp[-1] 复杂度分析 时间复杂度一次循环遍历每次循环执行的都是比较和赋值故 O ( n ) O(n) O(n)。空间复杂度用到长度n的数组dp存储中间状态故 O ( n ) O(n) O(n)。
def maxProfit(prices):if not prices:return 0n len(prices)dp [0] * nmin_price prices[0]for i in range(1, n):if prices[i] min_price:min_price prices[i]dp[i] max(dp[i - 1], prices[i] - min_price)return dp[-1]
