发帖
雷达卡
LeetCode 122题：股票买卖最大利润问题解析
在解决股票交易类算法题时，LeetCode 第122题允许进行无限次买入和卖出操作（但不能同时持有多支股票），目标是求出所能获得的最大利润。本文将采用动态规划的思想，并借助“现金钱包”与“股票钱包”的形象比喻，逐步拆解解题逻辑，并给出完整的 Java 实现代码。
题目描述
给定一个整数数组：
prices其中：
prices[i]表示第：
i天的股票价格。你可以进行多次交易（每次买入后必须先卖出才能再次买入）。要求计算能够获取的最大总利润。
示例说明
输入数据：
prices = [7,1,5,3,6,4]预期输出结果：
7过程解释：在第2天以价格1买入，在第3天以价格5卖出，获利4；接着在第4天以价格3买入，第5天以价格6卖出，获利3；累计总利润为7。
核心思路：动态规划建模
本题的关键在于使用动态规划维护两个状态变量，分别代表当前是否持有股票下的最优利润情况：
- 现金钱包（cash）：表示当前未持有股票时所拥有的最大利润。
- 股票钱包（stock）：表示当前持有股票时对应的最大利润（此时资金被锁定在股票中）。
每一天的操作都会基于前一天的状态做出决策：买入、卖出或保持不动。
状态转移规则
根据每日可执行的操作，定义如下状态更新方式：
- 今日不持有股票（cash）：可能是昨天就没有持股并继续空仓，也可能是今天将手中股票卖出。因此：
$cash = \max(\text{昨日cash},\ \text{昨日stock} + \text{今日价格})$ - 今日持有股票（stock）：可能是延续昨日持仓，也可能是用之前的现金在今天买入。故有：
$stock = \max(\text{昨日stock},\ \text{昨日cash} - \text{今日价格})$
初始条件设定
从第一天开始处理：
- 初始时没有买入任何股票，所以 cash = 0。
- 若要在第一天买入，则花费等于当天股价，即 stock = -prices[0]。
最终结果应取 cash 的值，因为在最后一天如果仍持有股票，显然不如将其卖出转化为实际利润更优。
Java代码实现
以下为完整实现，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，适用于任意长度的价格序列。
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int cash = 0; // 当前不持有股票的最大利润
int stock = -prices[0]; // 当前持有股票的最大利润（初始为买入第一天股票）
for (int i = 1; i < prices.length; i++) {
// 更新现金钱包：昨天持有今天卖出，或保持不持有
cash = Math.max(cash, stock + prices[i]);
// 更新股票钱包：昨天不持有今天买入，或保持持有
stock = Math.max(stock, cash - prices[i]);
}
return cash; // 最终不持有股票时利润最大
}
}代码逻辑详解
- 初始化阶段：
cashstock-prices[0]cash复杂度分析
- 时间复杂度：$O(n)$ —— 仅需对价格数组进行一次线性扫描。
- 空间复杂度：$O(1)$ —— 只使用了两个变量来维护状态，无需额外数组。
运行过程演示
以下是对输入：
prices = [7,1,5,3,6,4]的详细状态变化追踪表：
| 天数 | 价格 | 操作 | 现金钱包 | 股票钱包 | 说明 |
|---|---|---|---|---|---|
| 初始 | - | - | 0 | -∞ | 初始状态，尚未交易 |
| 1 | 7 | 买入 | 0 | -7 | 花费7元购入股票 |
| 2 | 1 | 买入（优化） | 0 | -1 | 发现更低价格，调整买入点至第2天 |
| 3 | 5 | 卖出 | 4 | -1 | 以5元售出，盈利4元 |
| 4 | 3 | 买入 | 4 | 1 | 动用已有利润买入，成本由账户承担 |
| 5 | 6 | 卖出 | 7 | 1 | 卖出获利3元，累计利润达7元 |
| 6 | 4 | 无操作 | 7 | 1 | 价格下跌，维持现状 |
最终利润为7，与程序输出一致。
关键要点归纳
- 状态设计是关键：通过定义
（不持股）和cash
（持股）两个状态，实现了对交易过程的精确建模。stock - 状态转换体现操作行为：
- 卖出行为：从
转移到stock
，增加收益；cash - 买入行为：从
转移到cash
，消耗资金。stock
- 卖出行为：从
- 支持无限次交易：由于每次卖出后 cash 增加，后续可用该利润继续买入，从而自然支持多轮买卖。
- 对比单次交易问题（如 LeetCode 121）：单次交易只需记录历史最低价与最大差价；而本题需要动态维护状态，策略更灵活，总体利润更高。
京公网安备 11010802022788号
