LeetCode 121 买卖股票的最佳时机——一文搞懂贪心算法思想前言很多人第一次接触贪心算法时都会有一个疑问什么叫贪心事实上LeetCode 121《买卖股票的最佳时机》就是最经典的贪心入门题。这道题没有复杂的数据结构也不需要动态规划只需要维护两个变量就能在一次遍历中求出最大利润。通过这篇文章你将彻底理解什么是贪心思想为什么一次遍历就能解决问题为什么要记录历史最低价格如何分析时间复杂度与空间复杂度一、题目描述给定一个数组prices。其中prices[i]表示第i天的股票价格。你只能进行一次交易买入一次卖出一次并且必须先买后卖求能够获得的最大利润。如果无法获得利润则返回0示例1prices[7,1,5,3,6,4]输出5解释第2天价格1买入 第5天价格6卖出 利润 6 - 1 5示例2prices[7,6,4,3,1]输出0解释价格持续下跌 不交易最优二、最容易想到的方法很多人第一反应是枚举买入日。再枚举卖出日。例如foriinrange(n):forjinrange(i1,n):profitprices[j]-prices[i]计算所有可能利润。然后取最大值。时间复杂度两层循环O(n²)如果n100000就会超时。因此需要更高效的方法。三、核心贪心思想观察题目。假设今天价格是6如果决定今天卖出。那么什么时候买最划算答案一定是今天之前价格最低的那一天。因为利润 卖出价格 - 买入价格想让利润最大卖出价格尽量高买入价格尽量低而卖出价格已经固定为今天。所以只需要知道历史最低价格即可。四、维护两个变量整个遍历过程中只需要维护1. 历史最低价格min_price表示到当前为止出现过的最低价格相当于最佳买入点。2. 最大利润max_profit表示目前为止能够获得的最大收益五、遍历时做什么对于每一天假设当前价格price需要做两件事。第一步计算今天卖出的利润如果今天卖出profitprice-min_price如果利润更大max_profitmax(max_profit,profit)第二步更新历史最低价格看看今天是不是更便宜min_pricemin(min_price,price)如果是。以后买入就选今天。六、完整执行过程模拟示例prices[7,1,5,3,6,4]初始化min_price∞ max_profit0第1天价格7利润7-∞无意义。最大利润0更新最低价min_price7第2天价格1利润1-7-6最大利润不变0更新最低价min_price1第3天价格5利润5-14更新max_profit4最低价保持1第4天价格3利润3-12小于4。不更新。第5天价格6利润6-15更新max_profit5第6天价格4利润4-13不更新。最终结果5七、完整代码实现fromtypingimportListclassSolution:defmaxProfit(self,prices:List[int])-int:min_pricefloat(inf)max_profit0forpriceinprices:# 今天卖出的利润profitprice-min_price# 更新最大利润ifprofitmax_profit:max_profitprofit# 更新历史最低价格ifpricemin_price:min_pricepricereturnmax_profit八、代码优化写法利用 Python 内置函数fromtypingimportListclassSolution:defmaxProfit(self,prices:List[int])-int:min_pricefloat(inf)max_profit0forpriceinprices:max_profitmax(max_profit,price-min_price)min_pricemin(min_price,price)returnmax_profit逻辑完全一致。代码更简洁。九、为什么这是贪心算法贪心思想核心每一步都选择当前最优决策。本题中对于每一天。都选择历史最低价格作为买入点因为这一定能让当天卖出的利润最大。不需要回头修改之前的选择。因此符合贪心策略。十、高频易错点1. 直接用全局最大值减全局最小值错误思路max(prices)-min(prices)例如[5,4,3,2,1]得到5-14但实际上5出现在1前面 无法先卖后买答案应该是02. min_price初始化为0错误min_price0会导致profitprice-0相当于0元买股票。明显不合理。正确float(inf)3. 返回负利润题目要求亏损时不交易因此答案最小只能是04. 使用双层循环虽然能做出来。但复杂度O(n²)无法通过大数据测试。十一、复杂度分析时间复杂度只遍历一次数组O(n)空间复杂度只使用两个变量O(1)十二、总结这道题是贪心算法最经典的入门题。核心思想可以总结为一句话遍历每一天记录历史最低价格假设今天卖出计算利润并更新最大收益。整个过程中维护两个变量min_price历史最低价格max_profit当前最大利润最终仅需一次遍历即可得到答案。掌握本题后建议继续练习LeetCode 122 买卖股票的最佳时机ⅡLeetCode 55 跳跃游戏LeetCode 45 跳跃游戏ⅡLeetCode 860 柠檬水找零这些题目都是贪心算法中的经典案例。