LeetCode 剑指 Offer 63. 股票的最大利润
目录
题目描述
题意分析
给出一支股票按时间排列的每日价格，只允许买入一次、卖出一次，求能获得的最大利润。若怎么操作都会亏，就不交易，利润记为 0。
「只能一次交易」意味着答案是某一对下标 $(i, j)$ 满足 $i < j$ 时的 $prices[j] - prices[i]$ 的最大值。$i < j$ 这个顺序约束是核心——不能拿后面的低价去买前面的高价。
约束信号：数组长度上限 $10^5$，价格是非负整数。规模要求线性；同时数组允许为空（长度可以是 0），此时没有任何交易机会，应返回 0。
边界情况：价格单调递减时任何交易都亏，返回 0；只有一天时买卖无法同时完成，返回 0；价格全部相同时利润为 0。
解法：一次扫描维护最低买入价
核心思路
暴力枚举买入日 $i$ 和卖出日 $j$ 会检查所有满足 $i < j$ 的组合，时间复杂度为 $O(n^2)$。重复计算发生在：对于每一个卖出日，都重新寻找它之前的最低价格。
固定第 $j$ 天卖出，最优买入价一定是
prices[0..j-1]的最小值。因此从左向右枚举卖出日时，只需同步维护历史最低价minPrice，当天可能得到的最大利润就是prices[j] - minPrice。循环开始处理第 $j$ 天之前，不变量是：
minPrice等于prices[0..j-1]的最小值；ans等于前 $j$ 天内所有合法交易的最大利润。先用第 $j$ 天尝试卖出，再把当天价格纳入历史最低价，循环结束后不变量自然推进一天。每一笔合法交易都对应某个卖出日；算法在该日使用了此前最低的买入价，得到的利润不会比任何同日卖出的方案差。所有卖出日都被检查，因此最终答案不会遗漏最优交易。
ans初始为 0，表示行情一直下跌时选择不交易。
解题步骤
- 若价格不足两天，无法完成一次先买后卖，直接返回 0。
- 用第一天价格初始化
minPrice，用 0 初始化ans。- 从第二天开始把每天都当作候选卖出日，先用
price - minPrice更新最大利润。- 再用当天价格更新
minPrice，供之后的卖出日使用。这个顺序让minPrice在计算利润时只包含严格更早的日期。- 扫描结束后返回
ans。以
prices = [7,1,5,3,6,4]为例：历史最低价依次从 7 降为 1；价格为 5 时利润更新为 4，价格为 6 时利润更新为 5。最终返回 5，对应价格 1 买入、价格 6 卖出。对于[7,6,4,3,1]，所有差值都不大于 0，ans保持 0。
代码实现
class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) {
return 0;
}
int minPrice = prices[0];
int ans = 0;
for (int i = 1; i < prices.length; i++) {
ans = Math.max(ans, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return ans;
}
}
func maxProfit(prices []int) int {
if len(prices) < 2 {
return 0
}
minPrice := prices[0]
ans := 0
for i := 1; i < len(prices); i++ {
if prices[i]-minPrice > ans {
ans = prices[i] - minPrice
}
if prices[i] < minPrice {
minPrice = prices[i]
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。每个价格只处理一次。
- 空间复杂度：$O(1)$。只维护历史最低价和最大利润。
关键点总结
- 固定卖出日后，最优买入价就是此前的最低价；这是把两层枚举降为一层扫描的关键。
minPrice只统计当前位置之前的价格，天然保证买入早于卖出，不能用全局最小值代替。ans = 0编码了“可以不交易”；如果题目要求必须交易一次，答案初值和边界处理都要改变。- 历史最低价是可滚动维护的前缀信息，不需要保存整个前缀数组。
- 面试时应先说清不变量和更新顺序，再说明这是“固定右端点、维护左侧最优值”的通用降维方式。
易错点总结
- 忽略交易顺序：直接计算全局最大值减全局最小值可能让买入发生在卖出之后。
[5,4,3,2,10,1]的正确答案是 8，不是 9。- 最低价初始化为 0：会凭空制造一个不存在的买入价。例如
[3,4]会错误地得到 4，而不是 1。- 答案允许为负数：单调下降时应选择不交易并返回 0，不能返回最大的负差值。
- 把一次交易当成多次交易：
[1,2,1,2]只能获得 1，不能把两段上涨利润累加为 2。- 未处理空数组：若用
prices[0]初始化最低价，必须先判断长度，否则会越界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 121. 买卖股票的最佳时机 | 简单 | 与本题同题，可直接对照标准表述 |
| 122. 买卖股票的最佳时机 II | 中等 | 交易次数不限，贪心累加所有上涨段 |
| 309. 买卖股票的最佳时机含冷冻期 | 中等 | 卖出后一天不能买，需引入第三个状态 |
| 714. 买卖股票的最佳时机含手续费 | 中等 | 每笔交易扣固定费用，转移时决定扣在买还是卖 |
| 123. 买卖股票的最佳时机 III | 困难 | 至多两次交易，四个状态串联推进 |
| 188. 买卖股票的最佳时机 IV | 困难 | 交易次数上限参数化为 $k$，状态多开一维 |