LeetCode 122. 买卖股票的最佳时机 II
题目描述
题意分析
prices[i]是第i天的股票价格，可以完成任意多次买入和卖出，但任何时刻最多持有一份股票，必须卖掉已有股票后才能继续买入。要求返回最终可以获得的最大利润，也可以选择完全不交易。与只能交易一次的版本不同，本题可以利用多段上涨。题目没有手续费、冷冻期或交易次数上限，同一天买入再卖出也不会产生额外收益；这些条件决定了各段交易可以自由衔接。
解法：贪心累加所有上涨差价
核心思路
[!blue]
先看一笔在第
a天买入、第b天卖出的交易。利润prices[b] - prices[a]等于持有期间所有相邻日差价之和，因为中间各天的价格会一加一减相互抵消。每个相邻日差价为正时，持有股票可以得到这部分上涨收益；差价为负时，持有反而承担亏损。因此，任意合法交易方案的总利润，都不可能超过“所有正相邻差价之和”：一份股票只能让每段差价贡献一次，负差价也不可能提高收益。
这个上界可以实际达到。把每一段连续上涨看作一次交易，在上涨开始前买入、上涨结束时卖出，获得的就是这一段全部正差价之和；下跌时不持仓，持平时是否合并相邻交易都不影响利润。各段按时间先后完成，始终不会同时持有多份股票。
既然正差价之和既是所有方案的上界，又有合法方案达到，就可以直接累加每一天相对前一天的正差价，不必显式保存买入、卖出的日期。
解题步骤
- 初始化累计利润
ans = 0。- 从第二天开始，比较当天价格与前一天价格。
- 若价格上涨，将
prices[i] - prices[i - 1]加入答案；下跌或持平则不增加收益。- 遍历结束后返回
ans。只有一天，或整个过程中都没有上涨时，答案自然为0。
代码实现
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
for (int i = 1; i < prices.length; i++) {
// 连续上涨的整段利润等于这些正相邻差价之和。
if (prices[i] > prices[i - 1]) {
ans += prices[i] - prices[i - 1];
}
}
return ans;
}
}
func maxProfit(prices []int) int {
ans := 0
for i := 1; i < len(prices); i++ {
// 连续上涨的整段利润等于这些正相邻差价之和。
if prices[i] > prices[i-1] {
ans += prices[i] - prices[i-1]
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，只遍历价格数组一次。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 一笔交易的首尾差价可以拆成持有期间的所有相邻差价。
- 正差价之和构成利润上界，按连续上涨段买卖又能达到这个上界。
- 计算时累加每日上涨，执行时可以合并为整段交易，两者收益完全相同。
解法：持有与空仓动态规划
核心思路
[!blue]
除了利用本题的贪心性质，也可以按每天结束时是否持有股票划分状态。
cash表示截至当天、手中没有股票时的最大现金余额；hold表示截至当天、持有一份股票时的最大现金余额，其中已经扣除了买入成本。两个状态保存各自条件下的最优方案，不要求来自同一条交易过程。今天空仓有两种来源：昨天就空仓，今天不操作；或者昨天持有，今天以
price卖出。因此cash = max(oldCash, oldHold + price)。今天持有也有两种来源：昨天就持有，今天继续持有；或者昨天空仓，今天以
price买入。因此hold = max(oldHold, oldCash - price)。买入只能从空仓状态转移，保证不会同时持有多份股票；卖出之后仍可再次买入，所以没有交易次数限制。第一天结束时，不买入的余额为
0，买入后的余额为-prices[0]。以后每天按上述两式更新。当天反复买卖没有额外收益，因此这两种状态已经覆盖最优决策；最终返回cash，代表股票已经卖出或从未买入的实际利润。
解题步骤
- 用第一天初始化
cash = 0、hold = -prices[0]。- 从第二天开始，先保存前一天的
oldCash、oldHold。- 比较继续空仓与今天卖出，得到新的
cash。- 比较继续持有与今天买入，得到新的
hold。- 返回最后一天的
cash。
代码实现
class Solution {
public int maxProfit(int[] prices) {
int cash = 0;
int hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
int oldCash = cash;
int oldHold = hold;
cash = Math.max(oldCash, oldHold + prices[i]);
hold = Math.max(oldHold, oldCash - prices[i]);
}
return cash;
}
}
func maxProfit(prices []int) int {
cash := 0
hold := -prices[0]
for i := 1; i < len(prices); i++ {
oldCash, oldHold := cash, hold
cash = max(oldCash, oldHold+prices[i])
hold = max(oldHold, oldCash-prices[i])
}
return cash
}
复杂度分析
- 时间复杂度：$O(n)$，每天只更新两个状态。
- 空间复杂度：$O(1)$，只保留前一天状态和更新所需的临时值。
关键点总结
[!green]
- 用是否持仓区分后续能否买入或卖出，同一天的不同方案分别保留最优余额。
- 卖出给余额加上当天价格，买入从余额扣除当天价格。
- 贪心直接收集所有上涨，动态规划显式描述持仓决策，两种方法在本题得到同一个最优值。
易错点总结
[!yellow]
- 套用只允许一次交易的逻辑，会遗漏卖出后重新买入获得的收益。
- 对相邻差价取绝对值，会把下跌也算成利润；本题不能通过做空从下跌中获利。
- 动态规划中的持有状态是扣除买入成本后的现金余额，不是股票价格，也不要求非负。
- 两个新状态应由前一天状态转移。先保留旧值再更新，可以直接对应递推含义。
- 最终返回空仓状态。若增加手续费、冷冻期或次数限制，应重新推导转移，不能继续无条件累加所有上涨。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 121. 买卖股票的最佳时机 | 简单 | 去掉只能交易一次的限制后，可以在多个上涨段分别获利。 |
| 714. 买卖股票的最佳时机含手续费 | 中等 | 加入每笔交易手续费后，不能简单把所有正差值相加，需要持有与空仓状态。 |
| 123. 买卖股票的最佳时机 III | 困难 | 以持有状态和交易次数描述每天的最优收益；本题允许重复买卖，该题最多完成两笔交易。 |
| 188. 买卖股票的最佳时机 IV | 困难 | 以持有状态和交易次数描述每天的最优收益；本题允许重复买卖，该题推广到 k 笔交易。 |
| 309. 买卖股票的最佳时机含冷冻期 | 中等 | 以持有状态和交易次数描述每天的最优收益；本题允许重复买卖，该题卖出后增加冷冻限制。 |