面试知识库

121. 买卖股票的最佳时机#

今天让我们一起深入探讨一个经典题目 - 买卖股票的最佳时机。这道题不仅在面试中常见，更重要的是它蕴含着一个重要的思维方式：如何在波动的数据中找到最优解。让我们用最直观的方式来理解这个问题。

📚 现实生活中的场景#

想象你是一个艺术品交易商。你有一件珍贵的艺术品，想要通过一次交易获得最大收益。你可以查看未来一段时间内这件艺术品的价格变化。问题是：在什么时候买入、什么时候卖出，才能获得最大收益呢？

问题描述#

题目目标#

给定一个数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。你只能选择某一天买入这只股票，并在未来某一天卖出，最多进行一次交易。请返回你能获得的最大利润；如果无法获得利润，返回 0。

示例 1#

输入： prices = [7,1,5,3,6,4] 输出： 5 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 问题的本质#

用直白的话说，就是：给你一个数组，数组中的第i个元素表示某个商品在第i天的价格。你只能选择其中的某一天买入，然后在这天之后的某一天卖出。问题是：你能获得的最大利润是多少？

比如说：

输入价格：[7,1,5,3,6,4]
最大利润：5（在第2天买入，价格=1；在第5天卖出，价格=6）
java

📝 解题思路的演进#

让我们看看解决这个问题的思维是如何发展的：

1. 暴力解法（不推荐）#

最直观的想法是：尝试所有可能的买入和卖出组合。但这样的时间复杂度是O(n²)，对于大规模数据来说非常低效。

2. 一次遍历解法（推荐）#

我们可以用一个更聪明的方式：在遍历过程中记录已经看到的最低价格，并尝试用当前价格减去这个最低价格来计算可能的利润。这样只需要遍历一次，时间复杂度是O(n)。

🎯 代码是如何工作的？#

让我们用具体的例子来理解算法的工作过程。 假设价格序列是：[7,1,5,3,6,4]

  1. 第一天（价格=7）：

    • minPrice = 7
    • maxProfit = 0

  2. 第二天（价格=1）：

    • 发现新的最低价：minPrice = 1
    • maxProfit 仍然是 0

  3. 第三天（价格=5）：

    • 当前利润 = 5 - 1 = 4
    • maxProfit 更新为 4

  4. 第四天（价格=3）：

    • 当前利润 = 3 - 1 = 2
    • maxProfit 保持 4

  5. 第五天（价格=6）：

    • 当前利润 = 6 - 1 = 5
    • maxProfit 更新为 5

  6. 第六天（价格=4）：

    • 当前利润 = 4 - 1 = 3
    • maxProfit 保持 5

🎨 让我们可视化这个过程#

🌟 面试时的要点#

  1. 理解问题约束

    • 只能进行一次交易（买入一次，卖出一次）
    • 必须先买入后卖出
    • 寻找的是最大利润，不是最高价格

  2. 解释算法思路

    • 为什么不用暴力解法
    • 如何通过记录最小值来优化
    • 时间复杂度和空间复杂度的分析

  3. 考虑边界情况

    • 空数组或只有一个元素的数组
    • 单调递减的价格序列
    • 价格都相同的情况

💡 相关的变种问题#

这个问题有几个常见的变种：

  1. 允许多次交易

    // 可以进行多次买卖，但不能同时进行多笔交易
public int maxProfitMultiple(int[] prices) {
    // profit：累计总利润，初始为 0
    int profit = 0;
    // 从第 1 天开始遍历，和前一天比较价格变化
    for (int i = 1; i < prices.length; i++) {
        // 如果今天比昨天贵，说明存在一段可获利的上升区间
        if (prices[i] > prices[i-1]) {
            // 把这段“今天 - 昨天”的正收益累加到总利润中
            profit += prices[i] - prices[i-1];
        }
    }
    // 返回多次交易下的最大累计利润
    return profit;
}
    java

  2. 限制交易次数

    // 最多进行k次交易
public int maxProfitWithKTransactions(int[] prices, int k) {
    // 需要使用动态规划来解决
    // 常见做法：定义“第 i 天、完成 t 次交易、是否持股”的状态并进行转移
    // 这里只给出方法签名作为扩展，不展开具体实现
}
    java

🎓 学习要点#

  1. 思维方式

    • 如何将复杂问题简化
    • 如何利用已知信息避免重复计算

  2. 代码优化

    • 使用变量记录状态
    • 一次遍历解决问题

  3. 实际应用

    • 在实际交易中的应用
    • 处理时间序列数据的思路

这道题看似简单，但它教会我们一个重要的思维方式：有时候，保持对历史最优值的追踪，能帮助我们更高效地解决问题。如果你对这个话题还有任何疑问，欢迎在评论区讨论！