Article / 文章
LeetCode 第121题：买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
题目描述
给定一个数组 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 <= 10^50 <= prices[i] <= 10^4
解题思路
方法一：暴力法
最直观的方法是使用两层循环，遍历所有可能的买入卖出组合，找出最大利润。
关键点：
- 外层循环遍历所有可能的买入日期
- 内层循环遍历所有可能的卖出日期（必须在买入日期之后）
- 计算每种组合的利润，并更新最大利润
具体步骤：
- 初始化最大利润为0
- 使用两层循环，外层循环i从0到n-2，内层循环j从i+1到n-1
- 对于每一对(i,j)，计算利润profit = prices[j] - prices[i]
- 如果profit大于当前最大利润，则更新最大利润
- 返回最大利润
时间复杂度：O(n²)，其中n是数组的长度，需要两层循环遍历所有可能的买入卖出组合 空间复杂度：O(1)，只需要常数级别的额外空间
方法二：一次遍历（贪心算法）
我们可以在遍历数组的同时，记录当前遇到的最低价格，并计算以当前价格卖出时的最大利润。
关键点：
- 记录遍历过程中遇到的最低价格
- 对于每个价格，计算如果在当前价格卖出的利润
- 更新最大利润
具体步骤：
- 初始化最大利润maxProfit为0，最低价格minPrice为一个很大的值（如int.MaxValue）
- 遍历数组prices，对于每个价格prices[i]： a. 如果prices[i]小于minPrice，则更新minPrice = prices[i] b. 计算当前利润profit = prices[i] - minPrice c. 如果profit大于maxProfit，则更新maxProfit = profit
- 返回maxProfit
时间复杂度：O(n)，其中n是数组的长度，只需要遍历一次数组 空间复杂度：O(1)，只需要常数级别的额外空间
方法三：动态规划
这个问题也可以用动态规划来解决。我们可以定义状态dp[i]表示前i天的最大利润。
关键点：
- 状态定义：dp[i]表示前i天的最大利润
- 状态转移方程：dp[i] = max(dp[i-1], prices[i] - minPrice)
- 其中minPrice是前i-1天的最低价格
具体步骤：
- 初始化dp数组，dp[0] = 0
- 初始化最低价格minPrice = prices[0]
- 遍历数组prices，从索引1开始： a. 更新dp[i] = max(dp[i-1], prices[i] - minPrice) b. 更新minPrice = min(minPrice, prices[i])
- 返回dp[n-1]
时间复杂度：O(n)，其中n是数组的长度，只需要遍历一次数组 空间复杂度：O(n)，需要一个长度为n的dp数组
图解思路
方法二：一次遍历过程
以示例1为例，prices = [7,1,5,3,6,4]
| 索引 | 价格 | 最低价格 | 当前利润 | 最大利润 | 说明 |
|---|---|---|---|---|---|
| 0 | 7 | 7 | 0 | 0 | 初始状态，最低价格为7，最大利润为0 |
| 1 | 1 | 1 | 0 | 0 | 更新最低价格为1，当前利润为0 |
| 2 | 5 | 1 | 4 | 4 | 最低价格仍为1，当前利润为5-1=4，更新最大利润为4 |
| 3 | 3 | 1 | 2 | 4 | 最低价格仍为1，当前利润为3-1=2，最大利润仍为4 |
| 4 | 6 | 1 | 5 | 5 | 最低价格仍为1，当前利润为6-1=5，更新最大利润为5 |
| 5 | 4 | 1 | 3 | 5 | 最低价格仍为1，当前利润为4-1=3，最大利润仍为5 |
最终结果：最大利润为5
方法三：动态规划过程
以示例1为例，prices = [7,1,5,3,6,4]
| 索引 | 价格 | 最低价格 | dp[i] | 说明 |
|---|---|---|---|---|
| 0 | 7 | 7 | 0 | 初始状态，dp[0] = 0 |
| 1 | 1 | 1 | 0 | dp[1] = max(dp[0], prices[1] - minPrice) = max(0, 1-7) = 0，更新minPrice = 1 |
| 2 | 5 | 1 | 4 | dp[2] = max(dp[1], prices[2] - minPrice) = max(0, 5-1) = 4 |
| 3 | 3 | 1 | 4 | dp[3] = max(dp[2], prices[3] - minPrice) = max(4, 3-1) = 4 |
| 4 | 6 | 1 | 5 | dp[4] = max(dp[3], prices[4] - minPrice) = max(4, 6-1) = 5 |
| 5 | 4 | 1 | 5 | dp[5] = max(dp[4], prices[5] - minPrice) = max(5, 4-1) = 5 |
最终结果：dp[5] = 5
代码实现
C# 实现
public class Solution {
// 方法一：暴力法（超时）
public int MaxProfitBruteForce(int[] prices) {
int maxProfit = 0;
int n = prices.Length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int profit = prices[j] - prices[i];
maxProfit = Math.Max(maxProfit, profit);
}
}
return maxProfit;
}
// 方法二：一次遍历（贪心算法）
public int MaxProfit(int[] prices) {
int maxProfit = 0;
int minPrice = int.MaxValue;
for (int i = 0; i < prices.Length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
int profit = prices[i] - minPrice;
maxProfit = Math.Max(maxProfit, profit);
}
}
return maxProfit;
}
// 方法三：动态规划
public int MaxProfitDP(int[] prices) {
if (prices.Length <= 1) {
return 0;
}
int n = prices.Length;
int[] dp = new int[n];
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.Max(dp[i - 1], prices[i] - minPrice);
minPrice = Math.Min(minPrice, prices[i]);
}
return dp[n - 1];
}
}Python 实现
class Solution:
# 方法一：暴力法（超时）
def maxProfitBruteForce(self, prices: List[int]) -> int:
max_profit = 0
n = len(prices)
for i in range(n - 1):
for j in range(i + 1, n):
profit = prices[j] - prices[i]
max_profit = max(max_profit, profit)
return max_profit
# 方法二：一次遍历（贪心算法）
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
min_price = float('inf')
for price in prices:
if price < min_price:
min_price = price
else:
profit = price - min_price
max_profit = max(max_profit, profit)
return max_profit
# 方法三：动态规划
def maxProfitDP(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
n = len(prices)
dp = [0] * n
min_price = prices[0]
for i in range(1, n):
dp[i] = max(dp[i - 1], prices[i] - min_price)
min_price = min(min_price, prices[i])
return dp[n - 1]C++ 实现
class Solution {
public:
// 方法一：暴力法（超时）
int maxProfitBruteForce(vector<int>& prices) {
int maxProfit = 0;
int n = prices.size();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int profit = prices[j] - prices[i];
maxProfit = max(maxProfit, profit);
}
}
return maxProfit;
}
// 方法二：一次遍历（贪心算法）
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
int minPrice = INT_MAX;
for (int i = 0; i < prices.size(); i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
int profit = prices[i] - minPrice;
maxProfit = max(maxProfit, profit);
}
}
return maxProfit;
}
// 方法三：动态规划
int maxProfitDP(vector<int>& prices) {
if (prices.size() <= 1) {
return 0;
}
int n = prices.size();
vector<int> dp(n, 0);
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
dp[i] = max(dp[i - 1], prices[i] - minPrice);
minPrice = min(minPrice, prices[i]);
}
return dp[n - 1];
}
};执行结果
C# 实现
- 执行用时：320 ms
- 内存消耗：45.8 MB
Python 实现
- 执行用时：240 ms
- 内存消耗：25.1 MB
C++ 实现
- 执行用时：96 ms
- 内存消耗：93.3 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 320 ms | 45.8 MB | 代码结构清晰，但性能较慢 |
| Python | 240 ms | 25.1 MB | 代码简洁，性能适中 |
| C++ | 96 ms | 93.3 MB | 执行速度最快，但内存占用较大 |
代码亮点
- 🎯 方法二通过一次遍历实现了O(n)的时间复杂度，大幅提升了效率
- 💡 贪心算法的思想：记录历史最低价格，并尝试在每个价格点卖出
- 🔍 动态规划方法清晰地定义了状态和转移方程，易于理解和扩展
- 🎨 代码结构清晰，变量命名规范，易于理解和维护
常见错误分析
- 🚫 没有考虑到股票价格可能一直下跌的情况，此时最大利润应为0
- 🚫 错误地认为可以在同一天买入和卖出股票
- 🚫 在动态规划方法中，没有正确初始化最低价格和dp数组
- 🚫 在暴力法中，没有正确处理边界情况，如数组长度小于2的情况
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 暴力法 | O(n²) | O(1) | 思路简单直观 | 效率低下，大规模数据会超时 |
| 一次遍历（贪心） | O(n) | O(1) | 效率高，空间占用小 | 不易扩展到更复杂的股票问题 |
| 动态规划 | O(n) | O(n) | 思路清晰，易于扩展 | 空间占用较大 |