121. 买卖股票的最佳时机
题目描述
输入数组 prices，prices[i] 是某支股票第 i 天的价格。
你最多只做一次交易：先在某一天买入一股，再在之后的另一天卖出。卖出日必须晚于买入日。
返回能得到的最大利润。如果怎么交易都赚不到钱，就不交易，返回 0。
示例 1
输入：prices = [7,1,5,3,6,4] 输出：5
解释：价格为 1 时买入、为 6 时卖出，利润 5；不能先以 7 卖出再以 1 买入。
示例 2
输入：prices = [7,6,4,3,1] 输出：0
解释：价格一路下跌，不交易，利润为 0。
数据范围
1 <= prices.length <= 10^50 <= prices[i] <= 10^4
解题思路：维护历史最低价
扫描价格，维护至今最低买入价，并用当前价减它更新利润。
为什么正确
扫描到当前位置时，best_buy 是此前最便宜的价格，profit 是此前可得最大利润。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
先更新最低价再计算差值仍然正确，因为当天买入不会产生正利润；不要允许卖出发生在买入之前。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
best_buy = float('inf')
profit = 0
for price in prices:
best_buy = min(best_buy, price)
profit = max(profit, price - best_buy)
return profitclass Solution {
public int maxProfit(int[] prices) {
int best_buy = Integer.MAX_VALUE;
int profit = 0;
for (int price : prices) {
best_buy = Math.min(best_buy, price);
profit = Math.max(profit, price - best_buy);
}
return profit;
}
}class Solution {
public:
int maxProfit(vector<int>& prices) {
int best_buy = INT_MAX;
int profit = 0;
for (int price : prices) {
best_buy = min(best_buy, price);
profit = max(profit, price - best_buy);
}
return profit;
}
};func maxProfit(prices []int) int {
best_buy := math.MaxInt
profit := 0
for _, price := range prices {
best_buy = min(best_buy, price)
profit = max(profit, price-best_buy)
}
return profit
}var maxProfit = function(prices) {
let best_buy = Infinity;
let profit = 0;
for (const price of prices) {
best_buy = Math.min(best_buy, price);
profit = Math.max(profit, price - best_buy);
}
return profit;
};function maxProfit(prices: number[]): number {
let best_buy = Infinity;
let profit = 0;
for (const price of prices) {
best_buy = Math.min(best_buy, price);
profit = Math.max(profit, price - best_buy);
}
return profit;
}其他解法
两种解法都是一次扫描、O(1) 空间；维护最低价从买入点角度思考，差分数组把问题归结为最大子段和。
解法 2：差分数组最大子段和 时间 O(n)，空间 O(1)
第 i 天买、第 j 天卖的利润，等于相邻两天价差在区间 (i, j] 上的和。问题转化为价差序列的最大子段和。用 Kadane 算法：cur = max(0, cur + 价差)，再用 cur 更新答案。
复杂度和主解法相同，但揭示了本题与「53. 最大子数组和」的联系。不如维护最低价直观。
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
cur = 0
profit = 0
for i in range(1, len(prices)):
cur = max(0, cur + prices[i] - prices[i - 1])
profit = max(profit, cur)
return profitclass Solution {
public int maxProfit(int[] prices) {
int cur = 0, profit = 0;
for (int i = 1; i < prices.length; i++) {
cur = Math.max(0, cur + prices[i] - prices[i - 1]);
profit = Math.max(profit, cur);
}
return profit;
}
}class Solution {
public:
int maxProfit(vector<int>& prices) {
int cur = 0, profit = 0;
for (int i = 1; i < (int)prices.size(); i++) {
cur = max(0, cur + prices[i] - prices[i - 1]);
profit = max(profit, cur);
}
return profit;
}
};func maxProfit(prices []int) int {
cur, profit := 0, 0
for i := 1; i < len(prices); i++ {
cur = max(0, cur+prices[i]-prices[i-1])
profit = max(profit, cur)
}
return profit
}var maxProfit = function(prices) {
let cur = 0, profit = 0;
for (let i = 1; i < prices.length; i++) {
cur = Math.max(0, cur + prices[i] - prices[i - 1]);
profit = Math.max(profit, cur);
}
return profit;
};function maxProfit(prices: number[]): number {
let cur = 0, profit = 0;
for (let i = 1; i < prices.length; i++) {
cur = Math.max(0, cur + prices[i] - prices[i - 1]);
profit = Math.max(profit, cur);
}
return profit;
}