Article / 文章
LeetCode 第122题：买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。 返回你能获得的 最大 利润。
题目描述
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回你能获得的 最大 利润。
难度
中等
题目链接
示例
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出，这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。提示
1 <= prices.length <= 3 * 10^40 <= prices[i] <= 10^4
解题思路
方法一：贪心算法
与第121题不同，这道题允许多次交易（买入卖出），但任何时候最多只能持有一股股票。贪心的思想是：只要今天的价格比昨天高，就在昨天买入，今天卖出，赚取差价。
关键点：
- 只关注相邻两天的价格差
- 只要价格上涨，就进行交易（买入卖出）
- 累加所有正的价格差，即为最大利润
具体步骤：
- 初始化最大利润maxProfit为0
- 遍历数组prices，从索引1开始： a. 计算当天与前一天的价格差diff = prices[i] - prices[i-1] b. 如果diff > 0，则将diff加到maxProfit上
- 返回maxProfit
时间复杂度：O(n)，其中n是数组的长度，只需要遍历一次数组 空间复杂度：O(1)，只需要常数级别的额外空间
方法二：动态规划
这个问题也可以用动态规划来解决。我们可以定义两个状态：
关键点：
- 状态定义：
- dp[i][0]表示第i天结束时不持有股票的最大利润
- dp[i][1]表示第i天结束时持有股票的最大利润
- 状态转移方程：
- dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
- dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
具体步骤：
- 初始化dp数组，dp[0][0] = 0, dp[0][1] = -prices[0]
- 遍历数组prices，从索引1开始： a. 更新dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) b. 更新dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
- 返回dp[n-1][0]（最后一天不持有股票的最大利润）
时间复杂度：O(n)，其中n是数组的长度，只需要遍历一次数组 空间复杂度：O(n)，需要一个二维dp数组
方法三：动态规划（空间优化）
我们可以发现，在方法二中，当前状态只与前一天的状态有关，因此可以使用两个变量来代替整个dp数组，从而优化空间复杂度。
关键点：
- 使用两个变量代替dp数组：
- cash表示当前不持有股票的最大利润
- hold表示当前持有股票的最大利润
- 状态转移方程保持不变
具体步骤：
- 初始化cash = 0, hold = -prices[0]
- 遍历数组prices，从索引1开始： a. 更新cash = max(cash, hold + prices[i]) b. 更新hold = max(hold, cash - prices[i])
- 返回cash
时间复杂度：O(n)，其中n是数组的长度，只需要遍历一次数组 空间复杂度：O(1)，只需要常数级别的额外空间
图解思路
方法一：贪心算法过程
以示例1为例，prices = [7,1,5,3,6,4]
| 索引 | 价格 | 价格差 | 是否交易 | 当前利润 | 累计利润 | 说明 |
|---|---|---|---|---|---|---|
| 0 | 7 | - | - | 0 | 0 | 初始状态 |
| 1 | 1 | -6 | 否 | 0 | 0 | 价格下跌，不交易 |
| 2 | 5 | 4 | 是 | 4 | 4 | 价格上涨，在第1天买入，第2天卖出 |
| 3 | 3 | -2 | 否 | 0 | 4 | 价格下跌，不交易 |
| 4 | 6 | 3 | 是 | 3 | 7 | 价格上涨，在第3天买入，第4天卖出 |
| 5 | 4 | -2 | 否 | 0 | 7 | 价格下跌，不交易 |
最终结果：最大利润为7
方法二：动态规划过程
以示例1为例，prices = [7,1,5,3,6,4]
| 索引 | 价格 | dp[i][0] | dp[i][1] | 说明 |
|---|---|---|---|---|
| 0 | 7 | 0 | -7 | 初始状态 |
| 1 | 1 | 0 | -1 | dp[1][0] = max(0, -7+1) = 0, dp[1][1] = max(-7, 0-1) = -1 |
| 2 | 5 | 4 | -1 | dp[2][0] = max(0, -1+5) = 4, dp[2][1] = max(-1, 0-5) = -1 |
| 3 | 3 | 4 | 1 | dp[3][0] = max(4, -1+3) = 4, dp[3][1] = max(-1, 4-3) = 1 |
| 4 | 6 | 7 | 1 | dp[4][0] = max(4, 1+6) = 7, dp[4][1] = max(1, 4-6) = 1 |
| 5 | 4 | 7 | 3 | dp[5][0] = max(7, 1+4) = 7, dp[5][1] = max(1, 7-4) = 3 |
最终结果：dp[5][0] = 7
代码实现
C# 实现
public class Solution {
// 方法一：贪心算法
public int MaxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.Length; i++) {
int diff = prices[i] - prices[i - 1];
if (diff > 0) {
maxProfit += diff;
}
}
return maxProfit;
}
// 方法二：动态规划
public int MaxProfitDP(int[] prices) {
int n = prices.Length;
int[,] dp = new int[n, 2];
// 初始状态
dp[0, 0] = 0; // 不持有股票
dp[0, 1] = -prices[0]; // 持有股票
for (int i = 1; i < n; i++) {
// 当前不持有股票的最大利润
dp[i, 0] = Math.Max(dp[i - 1, 0], dp[i - 1, 1] + prices[i]);
// 当前持有股票的最大利润
dp[i, 1] = Math.Max(dp[i - 1, 1], dp[i - 1, 0] - prices[i]);
}
return dp[n - 1, 0];
}
// 方法三：动态规划（空间优化）
public int MaxProfitDPOptimized(int[] prices) {
int cash = 0; // 不持有股票的最大利润
int hold = -prices[0]; // 持有股票的最大利润
for (int i = 1; i < prices.Length; i++) {
int prevCash = cash;
cash = Math.Max(cash, hold + prices[i]);
hold = Math.Max(hold, prevCash - prices[i]);
}
return cash;
}
}Python 实现
class Solution:
# 方法一：贪心算法
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
for i in range(1, len(prices)):
diff = prices[i] - prices[i - 1]
if diff > 0:
max_profit += diff
return max_profit
# 方法二：动态规划
def maxProfitDP(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0, 0] for _ in range(n)]
# 初始状态
dp[0][0] = 0 # 不持有股票
dp[0][1] = -prices[0] # 持有股票
for i in range(1, n):
# 当前不持有股票的最大利润
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
# 当前持有股票的最大利润
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
return dp[n - 1][0]
# 方法三：动态规划（空间优化）
def maxProfitDPOptimized(self, prices: List[int]) -> int:
cash = 0 # 不持有股票的最大利润
hold = -prices[0] # 持有股票的最大利润
for i in range(1, len(prices)):
prev_cash = cash
cash = max(cash, hold + prices[i])
hold = max(hold, prev_cash - prices[i])
return cashC++ 实现
class Solution {
public:
// 方法一：贪心算法
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
for (int i = 1; i < prices.size(); i++) {
int diff = prices[i] - prices[i - 1];
if (diff > 0) {
maxProfit += diff;
}
}
return maxProfit;
}
// 方法二：动态规划
int maxProfitDP(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
// 初始状态
dp[0][0] = 0; // 不持有股票
dp[0][1] = -prices[0]; // 持有股票
for (int i = 1; i < n; i++) {
// 当前不持有股票的最大利润
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
// 当前持有股票的最大利润
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
// 方法三：动态规划（空间优化）
int maxProfitDPOptimized(vector<int>& prices) {
int cash = 0; // 不持有股票的最大利润
int hold = -prices[0]; // 持有股票的最大利润
for (int i = 1; i < prices.size(); i++) {
int prevCash = cash;
cash = max(cash, hold + prices[i]);
hold = max(hold, prevCash - prices[i]);
}
return cash;
}
};执行结果
C# 实现
- 执行用时：88 ms
- 内存消耗：39.9 MB
Python 实现
- 执行用时：44 ms
- 内存消耗：17.8 MB
C++ 实现
- 执行用时：4 ms
- 内存消耗：12.9 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 88 ms | 39.9 MB | 代码结构清晰，但性能较慢 |
| Python | 44 ms | 17.8 MB | 代码简洁，性能适中 |
| C++ | 4 ms | 12.9 MB | 执行速度最快，内存占用最少 |
代码亮点
- 🎯 贪心算法简洁高效，直接累加所有正的价格差
- 💡 动态规划方法清晰地定义了状态和转移方程，易于理解和扩展
- 🔍 空间优化的动态规划方法将空间复杂度从O(n)降低到O(1)
- 🎨 三种方法各有优势，可以根据具体需求选择合适的实现
常见错误分析
- 🚫 没有理解题目允许多次交易的特性，错误地只进行一次交易
- 🚫 在动态规划方法中，没有正确定义状态或状态转移方程
- 🚫 在空间优化的动态规划方法中，没有使用临时变量保存上一个状态，导致状态更新错误
- 🚫 没有考虑到股票价格可能一直下跌的情况，此时最大利润应为0
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 贪心算法 | O(n) | O(1) | 简单直观，效率高 | 不易扩展到更复杂的股票问题 |
| 动态规划 | O(n) | O(n) | 思路清晰，易于扩展 | 空间占用较大 |
| 动态规划（空间优化） | O(n) | O(1) | 效率高，空间占用小 | 代码稍复杂 |