跳到主要内容

1 / 4思路

Best Time to Buy and Sell Stock

原题

思路​

一次遍历,维护“到今天为止的最低买入价”。每天用当前价格减去最低价得到候选利润,取最大值。先买后卖,所以更新利润后再更新最低价;顺序反了会允许当天买卖。

复杂度​

  • 时间 O(n):一次遍历。
  • 空间 O(1)。

代码​

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

边界​

  • 价格单调下降:没有正利润,返回 0。
  • 只有一天:无法完成买卖,返回 0。
  • 允许当天买卖时,best 会算出 0;题目要求利润非负,返回 0 仍正确。