1 / 4思路
Best Time to Buy and Sell Stock
思路
一次遍历,维护“到今天为止的最低买入价”。每天用当前价格减去最低价得到候选利润,取最大值。先买后卖,所以更新利润后再更新最低价;顺序反了会允许当天买卖。
复杂度
- 时间 O(n):一次遍历。
- 空间 O(1)。
代码
- Python
- TypeScript
def max_profit(prices: list[int]) -> int:
lowest = prices[0]
best = 0
for price in prices[1:]:
best = max(best, price - lowest)
lowest = min(lowest, price)
return best
function maxProfit(prices: number[]): number {
let lowest = prices[0];
let best = 0;
for (let index = 1; index < prices.length; index += 1) {
best = Math.max(best, prices[index] - lowest);
lowest = Math.min(lowest, prices[index]);
}
return best;
}
边界
- 价格单调下降:没有正利润,返回 0。
- 只有一天:无法完成买卖,返回 0。
- 允许当天买卖时,
best会算出 0;题目要求利润非负,返回 0 仍正确。