力扣面试经典——122题

💡 参考代码：

/**
 * 计算股票买卖的最大利润（可多次交易）
 * 
 * 算法思路：贪心策略，收集所有上涨段的利润
 * 核心思想：只要明天价格比今天高，就相当于今天买入明天卖出
 * 
 * @param prices 股票价格数组，prices[i]表示第i天的股票价格
 * @param pricesSize 数组长度，表示股票交易天数
 * @return 能获得的最大利润
 * 
 * 时间复杂度：O(n)，只需要遍历一次价格数组
 * 空间复杂度：O(1)，只使用常数额外空间
 * 
 * 示例：
 * prices = [7,1,5,3,6,4]
 * 第2天买入(1)，第3天卖出(5)：利润4
 * 第4天买入(3)，第5天卖出(6)：利润3
 * 总利润：7
 */
int maxProfit(int* prices, int pricesSize) {
    int profit = 0;  // 累计总利润
    
    // 从第2天开始遍历，比较相邻两天的价格
    for (int i = 1; i < pricesSize; i++) {
        // 如果今天价格高于昨天价格，说明可以获利
        // 相当于昨天买入今天卖出
        if (prices[i] > prices[i-1]) {
            profit += prices[i] - prices[i-1];  // 累加利润
        }
    }
    
    return profit;  // 返回最大利润
}

📖 总结：

点击展开题目总结

🤔 买卖股票的最佳时机Ⅱ

---

1️⃣ 题目核心信息

🎯 功能描述：给定股票每天的价格，计算在可以多次买卖的条件下能获得的最大利润，任何时候最多只能持有一股股票

📥 输入输出：

• 输入：int* prices（股票价格数组），int pricesSize（数组长度）
• 输出：int（能获得的最大利润）

---

2️⃣ 实现原理

💡 核心思路：贪心算法，收集所有上涨段的利润。只要相邻两天价格上涨就进行交易，相当于今天买入明天卖出

📋 实现步骤：

1. 初始化利润为0
2. 从第2天开始遍历价格数组
3. 比较当天与前一天的价格
4. 如果当天价格更高，则将差值加入总利润
5. 返回累计利润

---

3️⃣ 关键点解析

原始思路是寻找局部最优的买卖点，考虑各种复杂的买卖策略组合，但最优解采用贪心策略，将问题简化为收集所有上涨利润。

🎯 代码技巧

• 利用数学中的望远镜求和原理，将多次交易等价于最优的一次性交易
• 通过比较相邻元素差值来模拟交易决策
• 避免实际模拟买卖过程，直接计算理论最大收益

4️⃣ 使用场景

✅ 适用情况：

• 需要计算可多次交易情况下的最大理论收益
• 股票价格趋势分析
• 算法教学中的贪心策略示例

⚠️ 前提条件：

• 可以同一天买入并卖出
• 每次交易只持有一股股票
• 不考虑交易成本和税收

5️⃣ 复杂度分析

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

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

6️⃣ 注意事项

🚩 边界情况：

• 空数组或只有一个元素：返回0
• 价格持续下跌：返回0
• 价格持续上涨：返回首尾差值

💥 易错点：

• 误以为需要模拟真实的买卖过程
• 混淆与只能买卖一次的股票问题
• 忽略算法基于"预知未来"的假设条件

加载评论中...