文章目录一、[题目](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envTypestudy-plan-v2envIdtop-interview-150)二、My thinking三、动态规划3.1 动态规划算法3.2 算法步骤3.3 代码实现3.4 时间和空间复杂度四、总结一、题目给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票在第 i 天的价格。你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。示例1 输入[7,1,5,3,6,4]输出5解释在第2天股票价格1的时候买入在第5天股票价格6的时候卖出最大利润6-15。 注意利润不能是7-16,因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。 示例2 输入prices[7,6,4,3,1]输出0解释在这种情况下,没有交易完成,所以最大利润为0。二、My thinking求最大值但必须是后面元素减前面元素的最大。挨个遍历从第一个元素开始取后面所有元素的最大值与其相减将得到的差值替换掉第一个元素以此类推。最后求数组中除了最后一个元素的最大值代码实现classSolution:defmaxProfit(self,prices:list[int])-int:iflen(prices)1:return0forkinrange(len(prices)-1):if(m:max(prices[k1:len(prices)1]))prices[k]:prices[k]m-prices[k]else:prices[k]0returnmax(prices[0:len(prices)-1])结果超时了时间复杂度两层循环O(n²)返回时求最大值O(n)总的时间复杂度为 O(n²)O(n) ≈ O(n²)空间复杂度因为用到了切片总的空间复杂度为O(n)三、动态规划3.1 动态规划算法动态规划Dynamic programming DP将一个大问题分解为若干个重叠的子问题并通过保存子问题的解来避免重复计算从而高效解决原问题。核心思想记住求过的解。算法步骤参考菜鸟教程定义状态用一个或多个数组通常叫 dp来表示子问题的解。关键是弄清楚 dp[i] 或者 dp[i][j] 代表什么含义。确定状态转移方程找出 dp[i] 与之前状态如 dp[i-1], dp[i-2]之间的关系。这是动态规划的核心和难点。确定初始条件Base Case最小的、不可再分的子问题的解。这是递推的起点必须手动定义。确定计算顺序并计算确定是自顶向下记忆化递归还是自底向上循环递推。3.2 算法步骤在本题中因为要求最大利润并且后面元素减前面元素。要想得到最大利润必要要找到一个最低的买入点和最高的卖出点前提是买入在前卖出在后。可刚开始我们不知道最低买入点是多少那就先从第一个开始买此时利润值0这相当于确定了初始值往前走如果第二个元素 第一个不卖卖了就亏了更新将此元素确定为最低买入点。如果第二个 第一个卖了获得利润更新利润值。往前走依次往前遍历更新最低买入点 和 利润值。最后输出利润值。定义初始值和确定初始条件最低买入点min_price从第一个开始利润值 profit 0遍历数组中的元素并判断是否更新最低买入点 和 利润值返回利润值这样走下来每个元素就只需要遍历一次就OK了。和暴力超时的算法相比最大的优化就是用两个变量记住了之前的状态每走一步决定要不要更新优化之前的状态。3.3 代码实现classSolution:defmaxProfit(self,prices:list[int])-int:min_priceprices[0]profit0forpinprices:ifpmin_price:min_pricep# 更新历史最低买入价elifp-min_priceprofit:profitp-min_price# 更新最大利润returnprofit换成典型一点的动态规划写法classSolution:defmaxProfit(self,prices:List[int])-int:infint(1e9)minpriceinf# 给第一个元素也行maxprofit0forpriceinprices:# 下面两行就是状态转移方程记住了之前的状态每一步都和之前状态比一比决定是否优化maxprofitmax(price-minprice,maxprofit)minpricemin(price,minprice)returnmaxprofit 作者力扣官方题解 链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solutions/136684/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。换成二维DP写法classSolution:defmaxProfit(self,prices:list[int])-int:nlen(prices)ifn0:return0# dp[i][0]第 i 天不持有股票时的最大收益# dp[i][1]第 i 天持有股票时的最大收益dp[[0,0]for_inrange(n)]dp[0][0]0dp[0][1]-prices[0]# 第 0 天买入收益为负foriinrange(1,n):# 不持有昨天就不持有或今天卖出dp[i][0]max(dp[i-1][0],dp[i-1][1]prices[i])# 持有昨天就持有或今天买入本题只能买一次买入价即 -prices[i]dp[i][1]max(dp[i-1][1],-prices[i])returndp[n-1][0]3.4 时间和空间复杂度时间复杂度一层循环循环内做常数次操作时间复杂度为O(n)空间复杂度使用了常数次变量空间复杂度为O(1)四、总结本题是动态规划中最简单的一类定义两个初始变量遍历时去维护这两个变量的状态