买卖股票的最佳时机

#leetcode #2024/08/09 #算法/股票

目录

• 题目及理解
• 解题思路
  • 思路一
    • 代码实现
    • 复杂度分析
  • 思路二
• 错误记录

题目及理解

[!danger] 注意：只能买卖一次

解题思路

思路一

/**  
 * @description 解题思路  
 * ① base case: 如果 prices 为空，返回 0  
 * ② 初始化买入价格 buy 为 prices[0]，初始化利润 profit 为 0  
 * ③ 遍历 prices  
 *    1、如果当前价格比买入价格低，就更新买入价格  
 *    2、否则，更新利润  
 * ④ 返回利润  
 *     
 * */

代码实现

var maxProfit = function(prices) {  
    // base case  
    if (prices.length === 0) {  
        return 0;  
    }  
    // 买入价格  
    let buy = prices[0];  
    // 利润  
    let profit = 0;  
    // 遍历  
    for (let i = 1; i < prices.length; i++) {  
        // 如果当前价格比买入价格低，就更新买入价格  
        if (prices[i] < buy) {  
            buy = prices[i];  
        } else {  
            // 否则，计算利润  
            profit = Math.max(profit, prices[i] - buy);  
        }  
    }  
    return profit;  
};

复杂度分析

• 时间复杂度是 O(n)，其中 n 是价格数组的长度，因为我们只遍历了数组一次。
• 空间复杂度是 O(1)，因为我们只使用了两个额外的变量，不管输入规模如何，额外空间都是常数级的

思路二

买卖股票通用框架，见后文股票类型的题目

错误记录