买卖股票的最佳时机 - Stellar Observer Protocol

725 字

4 分钟

买卖股票的最佳时机

2025-08-08

Algorithms

数组

/

动态规划

题目描述#

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

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

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

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

解题思路#

初始化变量：
- 设置 minPrice 为第一天的价格
- 设置 maxProfit 为 0（至少可以不交易）
遍历价格数组：
- 更新历史最低价：minPrice = min(minPrice, currentminPrice = min(minPrice, currentPrice)
- 计算当前利润：currentProfit = currentPrice - minPrice
- 更新最大利润：maxProfit = max(maxProfit, currentProfit)
返回结果：
- 遍历结束后返回 maxProfit

关键洞察#

单次交易本质：
- 最大利润 = 某天价格 - 之前某天最低价
- 只需记录遍历过程中的历史最低点
无后效性：
- 后续价格只需与历史最低价比较，无需考虑更早状态
- 当前决策不影响后续决策（仅需知道历史最低价）
边界处理：
- 若价格单调递减，最大利润为 0（不交易）
- 首日价格直接作为初始 minPrice
算法选择：
- 贪心法效率最高（优于动态规划）
- 空间复杂度达到理论最优 O(1)

复杂度分析#

类型	复杂度	说明
时间复杂度	O(n)	遍历价格数组一次
空间复杂度	O(1)	仅需两个变量存储状态

代码实现#

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
        let newf0 = Math.max(f0, f2 - prices[i]);
10
        let newf1 = f0 + prices[i];
11
        let newf2 = Math.max(f1, f2);
12
        f0 = newf0;
13
        f1 = newf1;
14
        f2 = newf2;
15
    }
16
    return Math.max(f1, f2);
17
};

算法扩展性对比#

特性	动态规划	贪心算法
多交易扩展	易扩展到多交易场景(K次交易)	仅适用单次交易
冷冻期支持	可添加状态支持	无法处理
手续费支持	状态转移中可扣除手续费	需改造逻辑
理解难度	中等	简单直观

扩展：买卖股票最佳时机 II（无限交易）#

1
const maxProfit = (prices) => {
2
    let profit = 0;
3
    for (let i = 1; i < prices.length; i++) {
4
        if (prices[i] > prices[i - 1]) {
5
            profit += prices[i] - prices[i - 1];
6
        }
7
    }
8
    return profit;
9
};