数据结构和算法

喵～Master要写成一篇同学们也能轻松看懂的学习文章嘛？那我乖乖窝在你怀里，把两种算法整理成一篇既清晰又有点可爱的小教程给你 ❤️(=˃ᆺ˂=)ﾉ

🐾 一文搞懂股票买卖最大利润问题（含最佳买卖日）

在学习算法时，“股票买卖最大利润”这一题几乎是所有人都会遇到的经典练习。
题目是这样哒：

给定一个数组 prices，prices[i] 代表股票第 i 天的价格。
你只能选择 一天买入，并在 未来某一天卖出。
请计算 你能获得的最大利润。

这篇文章我们会从基础算法讲起，再到升级算法（返回最佳买卖日），帮助你一步步掌握思维过程。

🐱 一、基础版算法：只求最大利润

✨ 核心思路

为了赚到最多的“小鱼干”（利润）：

  1. 遍历价格数组，记录历史最低价
  2. 当作如果今天卖出，能赚多少
  3. 不停更新“最大利润”

只需要一次遍历，时间复杂度 O(n)，非常高效。

🧩 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
def maxProfit(prices):
    if not prices or len(prices) < 2:
        return 0

    min_price = prices[0]   
    max_profit = 0          

    for price in prices[1:]:
        max_profit = max(max_profit, price - min_price)
        min_price = min(min_price, price)

    return max_profit

💡 用例讲解

以 prices = [7,1,5,3,6,4] 为例：

  • 最便宜是在第 1 天：1
  • 最合适卖出是在第 4 天：6
  • 最大利润 = 6 - 1 = 5

这个版本已经能准确告诉你能赚多少钱啦！

但同学们可能会问：

“我想知道到底是哪一天买、哪一天卖比较好呢？”

那么我们就进入升级版啦～

🐾 二、升级版算法：返回最大利润 + 买入日 + 卖出日

为了让结果更可视化、更实用，我们不仅算利润，还要告诉你：

✔ 什么时候买最便宜
✔ 哪一天卖收益最高
✔ 最终能赚多少

✨ 核心思路升级

和基础版类似，只是额外记录：

  • min_day：最低价那一天
  • buy_day / sell_day：最终最佳组合

每当发现更高利润，就同步更新买卖日。

🧩 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def maxProfit_with_days(prices):
    if not prices or len(prices) < 2:
        return 0, -1, -1

    min_price = prices[0]
    min_day = 0
    max_profit = 0
    buy_day = 0
    sell_day = 0

    for i in range(1, len(prices)):
        price = prices[i]

        # 如果今天卖更划算，就更新
        if price - min_price > max_profit:
            max_profit = price - min_price
            buy_day = min_day
            sell_day = i

        # 如果遇到新的更低价格，更新最低价位置
        if price < min_price:
            min_price = price
            min_day = i

    return max_profit, buy_day, sell_day

🐱 举例

同样用 [7,1,5,3,6,4]：

输出会是：

1
(5, 1, 4)

✔ 最大利润 = 5
✔ 第 1 天买入
✔ 第 4 天卖出
这正是最优方案！

🐾 三、两种算法对比总结

功能 基础版 升级版
最大利润 ✔ ✔
返回买入日 ✘ ✔
返回卖出日 ✘ ✔
时间复杂度 O(n) O(n)
人性化程度 基础计算 更实用、更直观

如果只是需计算收益，基础版足够；
如果要展示过程、用于教学或做可视化，升级版更适合同学们学习。

🎀 四、写在最后的小贴心提示

这个题目虽然简单，但它体现了算法设计里非常重要的思想：

  • 用一趟遍历解决问题
  • 在遍历过程中同步更新最优解
  • 记录关键状态（如最低价及其出现时间）

掌握这一题，你会发现许多动态规划、贪心思维的题目都会用到类似技巧喵～

Master如果想继续学习：

✨ 多次交易版本
✨ 带手续费版本
✨ 带冷冻期（cooldown）的版本
✨ 使用图形来展示买卖过程

我都会乖乖把答案献给你哒~(=´ᆺ`=)ノ💗