买卖股票的最佳时机含冷冻期 - Stellar Observer Protocol

605 字

3 分钟

买卖股票的最佳时机含冷冻期

2025-08-28

Algorithms

数组

/

动态规划

题目描述#

给定一个整数数组prices，其中第 prices[i] 表示第 _i_ 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解题思路#

状态机建模：
- 定义三种状态：持有股票、不持有股票（可买入）、冷冻期
状态转移方程：
- 持有股票：继承前持仓或从非冷冻期买入
- 冷冻期：只能来自卖出操作
- 非冷冻期：继承前非冷冻期或冷冻期结束
动态规划：
- 创建三元组表示各状态最大收益
- 每日更新状态值
边界初始化：
- 起始可直接买入
- 冷冻期初始为零
结果输出：
- 最终取不持仓和冷冻期最大值

关键洞察#

状态分离必要性：
- 冷冻期限制需区分可买入/不可买入状态
状态转移逻辑：
- 买入仅限非冷冻期状态
- 卖出后必进冷冻期
空间优化：
- 仅需前日状态，空间可降至O(1)
收益最大化：
- 最终不持仓收益高于持仓
决策完备性：
- 三种状态覆盖所有操作可能

复杂度分析#

指标	说明
时间复杂度	O(n)：单次遍历价格序列
空间复杂度	O(1)：仅需常量状态变量
最优情况	O(n)：必须遍历完整价格序列
最坏情况	O(n)：股价持续下跌时仍需完整计算

代码实现#

1
/**
2
 * @param {number[]} prices
3
 * @return {number}
4
 */
5
var maxProfit = function (prices) {
6
    if (!prices || prices.length === 0) return 0;
7
    let f0 = -prices[0], f1 = 0, f2 = 0;
8
    for (let i = 1, n = prices.length; i < n; i++) {
9
        const new_f0 = Math.max(f0, f2 - prices[i]);
10
        const new_f1 = f0 + prices[i];
11
        const new_f2 = Math.max(f1, f2);
12
        f0 = new_f0;
13
        f1 = new_f1;
14
        f2 = new_f2;
15
    }
16
    return Math.max(f1, f2);
17
};