力扣面试经典——121题

💡 参考代码：

/**
 * 计算股票交易的最大利润
 * 
 * 给定一个数组，它的第i个元素是一支给定股票第i天的价格。
 * 只能选择某一天买入股票，并选择在未来的某一个不同的日子卖出该股票。
 * 设计一个算法来计算所能获取的最大利润。
 * 
 * @param prices 整数数组，表示股票每天的价格
 * @param pricesSize 数组prices的长度
 * @return 返回能获取的最大利润，如果不能获取任何利润则返回0
 * 
 * 示例:
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解释: 在第2天买入(价格=1)，在第5天卖出(价格=6)，利润=6-1=5
 * 
 * 输入: [7,6,4,3,1]
 * 输出: 0
 * 解释: 价格持续下跌，无法获得利润
 * 
 * 时间复杂度: O(n)
 * 空间复杂度: O(1)
 */
int maxProfit(int* prices, int pricesSize) {
    // 如果天数少于2天，无法完成交易，返回0
    if (pricesSize <= 1) {
        return 0;
    }
    
    // 初始化最低价格为第一天的价格
    int minPrice = prices[0];
    // 初始化最大利润为0
    int maxProfit = 0;
    
    // 从第二天开始遍历所有价格
    for (int i = 1; i < pricesSize; i++) {
        // 如果当前价格比记录的最低价格更低，则更新最低价格
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } 
        // 如果当前价格与最低价格的差值大于记录的最大利润，则更新最大利润
        else if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }
    
    return maxProfit;
}

📖 总结：

点击展开题目总结

🤔 买卖股票的最佳时机

---

1️⃣ 题目核心信息

🎯 功能描述：给定股票价格数组，找出买入和卖出股票能获得的最大利润，只能进行一次交易且卖出日必须在买入日之后

📥 输入输出：

• 输入：int* prices（股票价格数组）, int pricesSize（数组长度）
• 输出：int（最大利润值，无法获利时返回0）

---

2️⃣ 实现原理

💡 核心思路：一次遍历动态维护最低买入价格和最大利润

📋 实现步骤：

1. 初始化最低价格为第一天价格，最大利润为0
2. 从第二天开始遍历价格数组
3. 若当前价格低于最低价格，则更新最低价格
4. 否则计算当前卖出可得利润，若大于最大利润则更新最大利润
5. 遍历结束返回最大利润

---

3️⃣ 关键点解析

原始思路是使用快慢指针枚举所有买入卖出组合，通过两层循环计算每种可能的利润并取最大值。但该方法时间复杂度为O(n²)。最优解通过记录到目前为止的最低价格和最大利润，只需一次遍历就能得到结果，时间复杂度优化为O(n)。

🎯 代码技巧

• 使用else if避免不必要的利润计算
• 初始化最低价格为第一个元素，从第二个元素开始遍历
• 利用贪心思想，始终维护到目前为止的最优解

4️⃣ 使用场景

✅ 适用情况：

• 股票交易利润最大化问题
• 需要找出数组中两个元素的最大正向差值
• 在线算法需要实时更新最优解

⚠️ 前提条件：

• 卖出日必须在买入日之后
• 只能进行一次交易
• 数组元素为非负整数

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n)，只需遍历数组一次

• 💾 空间复杂度：O(1)，只使用常数个额外变量

6️⃣ 注意事项

🚩 边界情况：

• 数组长度为0或1时，无法完成交易
• 价格持续下跌时，利润为0
• 数组为空指针的情况

💥 易错点：

• 忘记处理数组长度小于2的边界情况
• 错误地允许在买入前卖出
• 没有正确初始化最小价格和最大利润

加载评论中...