买卖股票的最佳时机
🟢 简单题目描述
给定一个数组 prices，它的第 i 个元素 prices[i] 是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一只股票），设计一个算法来计算你所能获取的最大利润。
示例 1
输入：[7, 1, 5, 3, 6, 4]
输出：5
解释：在第 2 天买入（价格 = 1），在第 5 天卖出（价格 = 6），最大利润 = 6 - 1 = 5示例 2
输入：[7, 6, 4, 3, 1]
输出：0
解释：在这种情况下，没有交易完成，最大利润为 0提示
1 <= prices.length <= 10^50 <= prices[i] <= 10^4
解法一
参考答案 (2 个标签)
暴力枚举 O(n²)
思路
枚举所有买入和卖出的组合，计算最大利润。
代码实现
/**
* @param {number[]} prices
* @return {number}
*/
function maxProfit(prices) {
let maxProfit = 0;
for (let i = 0; i < prices.length - 1; i++) {
for (let j = i + 1; j < prices.length; j++) {
maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
}
}
return maxProfit;
}复杂度分析
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
解法二
参考答案 (2 个标签)
一次遍历 O(n)
思路
遍历过程中记录历史最低价，计算当前价格与最低价的差值（利润），更新最大利润。
代码实现
/**
* @param {number[]} prices
* @return {number}
*/
function maxProfit(prices) {
let minPrice = Infinity;
let maxProfit = 0;
for (const price of prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
图解
prices: [7, 1, 5, 3, 6, 4]
i=0: price=7, minPrice=7, maxProfit=0
i=1: price=1, minPrice=1, maxProfit=0
i=2: price=5, minPrice=1, maxProfit=4
i=3: price=3, minPrice=1, maxProfit=4
i=4: price=6, minPrice=1, maxProfit=5
i=5: price=4, minPrice=1, maxProfit=5
返回 5