这道题是股票系列的第一题也是最简单的一题——只允许交易一次。虽然简单但它奠定了一个核心思路“遍历到第 i 天时我只需要知道之前的最小值”。这个只关心历史最优的思想贯穿了整个股票系列。题目长什么样给定一个数组pricesprices[i]表示第i天的股票价格。你只能选择某一天买入并在未来的某一天卖出。计算你能获取的最大利润。如果不能获利返回0。输入prices [7,1,5,3,6,4]输出5说人话就是找一个最低点买入、之后的最高点卖出算最大差价。注意买入必须在卖出之前。第一反应两层循环暴力枚举最直接的想法——枚举每一对买入/卖出日期找最大差值。classSolutionBrute:defmaxProfit(self,prices:List[int])-int:max_profit0foriinrange(len(prices)):forjinrange(i1,len(prices)):profitprices[j]-prices[i]ifprofitmax_profit:max_profitprofitreturnmax_profit维度值说明时间O(n²)n 最大 10^5铁定超时空间O(1)暴力法的问题很明显对于每一天我们都重新扫描了它后面的所有天。但实际上当我站在第i天卖出时我只需要知道之前哪天最便宜就行了不需要再枚举所有可能的买入日。最优解一次遍历维护历史最低价思路非常简单遍历每一天的价格 - 如果今天的价格比历史最低价还低 → 更新最低价今天适合买入 - 否则 → 计算今天卖出的利润今天价格 - 历史最低价更新最大利润classSolution:defmaxProfit(self,prices:List[int])-int:min_priceprices[0]max_profit0forpriceinprices[1:]:ifpricemin_price:min_pricepriceelifprice-min_pricemax_profit:max_profitprice-min_pricereturnmax_profit为什么这样做是对的关键观察最大利润 某天的价格 - 之前某天的最低价格。当我们遍历到第i天时min_price记录了prices[0]到prices[i-1]的最小值。那么prices[i] - min_price就是以第i天为卖出日能获得的最大利润。我们只需要在所有天数中取最大值即可。这里用了一个贪心的思想不需要记住在哪天买入只需要记住最低价是多少。跑一遍示例 1prices [7, 1, 5, 3, 6, 4] Day 0: min_price 7, max_profit 0 (初始化) Day 1: price 1 1 7 → 更新 min_price 1 min_price1, max_profit0 Day 2: price 5 5 1, profit 5 - 1 4 0 → 更新 max_profit 4 min_price1, max_profit4 Day 3: price 3 3 1, profit 3 - 1 2 4 → 不更新 min_price1, max_profit4 Day 4: price 6 6 1, profit 6 - 1 5 4 → 更新 max_profit 5 min_price1, max_profit5 Day 5: price 4 4 1, profit 4 - 1 3 5 → 不更新 min_price1, max_profit5 最终: max_profit 5 (Day 1 买入, Day 4 卖出)跑一遍示例 2prices [7, 6, 4, 3, 1] Day 0: min_price 7 Day 1: 6 7 → min_price 6 Day 2: 4 6 → min_price 4 Day 3: 3 4 → min_price 3 Day 4: 1 3 → min_price 1 全程没进过 elif 分支 → max_profit 0 (无法盈利)维度值说明时间O(n)一次遍历空间O(1)只用了两个变量两种解法放在一起看解法时间空间思路暴力枚举O(n²)O(1)枚举所有买入/卖出对一次遍历O(n)O(1)维护历史最低价贪心更新最大利润暴力法的冗余在于对每个卖出日都重新遍历了之前的所有买入日。而实际上之前的最小值只需要一个变量就能维护——这就是 O(n²) 到 O(n) 的优化。这道题教会我什么只需要知道历史最优是一个通用模式这道题的核心操作是price - min_price。我们不需要知道min_price出现在第几天不需要知道之前的完整价格走势只需要一个数字——历史最低价。这种只关心历史最优/最值的模式在很多题目里都能看到最大子数组和LeetCode 53只关心以当前位置结尾的最大和爬楼梯LeetCode 70只关心前两步的方案数股票系列后续题目维护不同的状态变量贪心每一步做局部最优选择这道题是贪心算法的典型案例。我们没有尝试所有可能的交易组合而是在每一天做一个简单的决策今天的价格是否足以刷新最大利润如果是就更新如果不是就跳过。因为题目只允许一次交易所以这个贪心策略是正确的。边界价格一直下跌当价格单调递减时max_profit始终为 0代码自动处理了这种情况。不需要额外判断——因为elif分支永远不会进入max_profit保持初始值 0。这也是为什么初始值设为 0 而不是负无穷的原因。完整测试代码fromtypingimportListclassSolution:defmaxProfit(self,prices:List[int])-int:min_priceprices[0]max_profit0forpriceinprices[1:]:ifpricemin_price:min_pricepriceelifprice-min_pricemax_profit:max_profitprice-min_pricereturnmax_profitif__name____main__:sSolution()prices[7,1,5,3,6,4]print(f输入:{prices}, 输出:{s.maxProfit(prices)})prices[7,6,4,3,1]print(f输入:{prices}, 输出:{s.maxProfit(prices)})prices[2,4,1]print(f输入:{prices}, 输出:{s.maxProfit(prices)})prices[3]print(f输入:{prices}, 输出:{s.maxProfit(prices)})prices[1,2]print(f输入:{prices}, 输出:{s.maxProfit(prices)})相关题目推荐LeetCode 122 · 买卖股票的最佳时机 II允许多次交易贪心/DPLeetCode 123 · 买卖股票的最佳时机 III最多两次交易状态机 DPLeetCode 53 · 最大子数组和同样的维护历史最优思想