忍者算法

Appearance

买卖股票的最佳时机：从波峰波谷中寻找最大利润！ ​

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

📚 现实生活中的场景 ​

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

💡 问题的本质 ​

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

比如说：

java
输入价格：[7,1,5,3,6,4]
最大利润：5（在第2天买入，价格=1；在第5天卖出，价格=6）
java
class Solution {
    public int maxProfit(int[] prices) {
        // 如果价格数组为空或只有一天的价格，无法交易
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        
        // 记录到目前为止的最低价格（潜在的买入点）
        int minPrice = prices[0];
        // 记录最大利润
        int maxProfit = 0;
        
        // 遍历每一天的价格
        for (int i = 1; i < prices.length; i++) {
            // 如果找到了更低的价格，更新最低价格
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                // 尝试在当前价格卖出，看看能否获得更大利润
                int currentProfit = prices[i] - minPrice;
                maxProfit = Math.max(maxProfit, currentProfit);
            }
        }
        
        return maxProfit;
    }
}

📝 解题思路的演进 ​

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

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

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

svg
<svg viewBox="0 0 600 400" xmlns="http://www.w3.org/2000/svg">
  <!-- 背景 -->
  <rect width="600" height="400" fill="#f8f9fa"/>
  
  <!-- 坐标轴 -->
  <line x1="50" y1="350" x2="550" y2="350" stroke="black" stroke-width="2"/>
  <line x1="50" y1="50" x2="50" y2="350" stroke="black" stroke-width="2"/>
  
  <!-- 价格曲线 -->
  <path d="M 100 200 L 180 320 L 260 240 L 340 280 L 420 220 L 500 260" 
        fill="none" stroke="#2196f3" stroke-width="3"/>
  
  <!-- 最佳买入点 -->
  <circle cx="180" cy="320" r="6" fill="#4caf50"/>
  <text x="160" y="340" fill="#4caf50">买入点</text>
  
  <!-- 最佳卖出点 -->
  <circle cx="420" cy="220" r="6" fill="#f44336"/>
  <text x="400" y="200" fill="#f44336">卖出点</text>
  
  <!-- 最大利润区间 -->
  <path d="M 180 320 L 420 320 L 420 220 L 180 320" 
        fill="#2196f3" fill-opacity="0.1" stroke="#2196f3" stroke-dasharray="5,5"/>
  
  <!-- 坐标轴标签 -->
  <text x="300" y="380" text-anchor="middle">时间</text>
  <text x="30" y="200" text-anchor="middle" transform="rotate(-90 30 200)">价格</text>
  
  <!-- 说明文字 -->
  <text x="300" y="100" text-anchor="middle" font-size="14">最大利润 = 卖出价 - 买入价</text>
</svg>

🌟 面试时的要点 ​

  1. 理解问题约束

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

  2. 解释算法思路

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

  3. 考虑边界情况

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

💡 相关的变种问题 ​

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

  1. 允许多次交易

    java
    // 可以进行多次买卖，但不能同时进行多笔交易
public int maxProfitMultiple(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i-1]) {
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
}

  2. 限制交易次数

    java
    // 最多进行k次交易
public int maxProfitWithKTransactions(int[] prices, int k) {
    // 需要使用动态规划来解决
}

🎓 学习要点 ​

  1. 思维方式

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

  2. 代码优化

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

  3. 实际应用

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

作者：忍者算法 公众号：忍者算法 🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步 #算法面试 #LeetCode #动态规划 #贪心算法

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