当前位置：首页 > news >正文

【LeetCode 热题 100】121. 买卖股票的最佳时机

news 2025/8/16 15:45:30

Problem: 121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(1)

整体思路

这段代码旨在解决一个非常经典的股票交易问题：买卖股票的最佳时机 I (Best Time to Buy and Sell Stock)。问题要求在给定的一系列每日股票价格中，通过一次买入和一次卖出交易，找到能够获得的最大利润。如果无法获利（即价格一直在下跌），则最大利润为0。

该算法采用了一种非常高效的 单次遍历（Single Pass） 贪心策略。其核心思想是在遍历价格数组的过程中，动态地维护两个关键信息：

历史最低价格 (Historical Minimum Price)：记录到当前日期为止，所遇到的股票的最低价格。
最大利润 (Maximum Profit)：记录到当前日期为止，通过在历史最低点买入、在某一天卖出所能实现的最大收益。

算法的具体执行步骤如下：

初始化：
- 创建一个变量 minPrice，用于存储历史最低价格。它被初始化为第一天的价格 prices[0]。
- 创建一个变量 ans，用于存储最大利润。它被初始化为 0，因为如果没有任何交易可以获利，利润就是0。
单次遍历：
- 算法通过一个 for 循环，从左到右遍历整个 prices 数组。每一次迭代都可以看作是时间向前推移一天。
- 在循环的每一天（对应价格 p），算法会执行两个关键操作，且顺序非常重要：
  a. 计算潜在利润并更新最大利润：首先，算法假设今天是卖出日。它会计算今天卖出的价格 p 与之前的历史最低买入价 minPrice 之间的差值，即 p - minPrice。这个差值就是如果在历史最低点买入、在今天卖出所能获得的利润。然后，用这个潜在利润与已记录的最大利润 ans 进行比较，并将 ans 更新为较大者。
  b. 更新历史最低价格：在完成利润计算之后，算法会用今天的价格 p 来更新 minPrice。即比较当前的 minPrice 和今天的 p，并将 minPrice 更新为较小者。这样做是为了给未来的日子提供一个更新后的、可能更低的买入价格。
返回结果：
- 当遍历完所有价格后，ans 变量中就存储了在整个时间段内进行一次交易所能获得的最大利润。将其返回即可。

这个算法的巧妙之处在于，它通过一次遍历就解决了问题。在每一天，它都利用过去的信息（minPrice）来做当前的最优决策（更新ans），同时更新自身状态（更新minPrice）以供未来使用。

完整代码

class Solution {/*** 计算只进行一次买卖股票交易能获得的最大利润。* @param prices 每日股票价格的数组* @return 最大利润*/public int maxProfit(int[] prices) {// minPrice: 用于记录到目前为止遇到的最低股票价格。// 初始化为第一天的价格，作为比较的起点。int minPrice = prices[0];// ans: 用于存储找到的最大利润。// 初始化为 0，因为如果无法获利，最大利润就是 0。int ans = 0;// 遍历价格数组，p 代表当天的价格for (int p : prices) {// 关键步骤 1: 计算今天卖出能获得的最大利润。// p 是今天的卖出价，minPrice 是在今天之前能买入的最低价。// 用这个潜在的利润去更新全局的最大利润 ans。// 这个操作必须在更新 minPrice 之前，因为不能在同一天买入又卖出。ans = Math.max(ans, p - minPrice);// 关键步骤 2: 更新历史最低价格。// 用今天的价格 p 和已记录的最低价 minPrice 比较，// 并将 minPrice 更新为更小的值，供未来的日子计算利润时使用。minPrice = Math.min(minPrice, p);}// 遍历结束后，ans 中存储的就是整个时间段内的最大利润return ans;}
}

时空复杂度

时间复杂度：O(N)

循环：算法的核心是一个 for-each 循环，它遍历 prices 数组中的每一个元素一次。如果数组的长度为 N，这个循环将执行 N 次。
循环内部操作：
- 在循环的每一次迭代中，只执行了两次 Math.max/Math.min 操作和一次减法操作。
- 这些操作都是基本运算，其时间复杂度为 O(1)。