121. 买卖股票的最佳时机（Best Time to Buy and Sell Stock）

频次 ★★★★ · 难度 🟢 · 高频：全厂

题目

给定一个数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。你最多只能完成一笔交易（买入一次 + 卖出一次），求最大利润。注意：不能在同一天买入和卖出，且必须先买入再卖出。

示例：

输入: prices = [7,1,5,3,6,4]
输出: 5
解释: 第 2 天买入(价格=1)，第 5 天卖出(价格=6)，利润 = 5

思路

一次遍历，维护两个变量：

• minPrice：到当前位置的最低价格（最佳买入点）
• maxProfit：到当前位置的最大利润

遍历时更新最低价，并用当前价格减去最低价更新最大利润。本质上是在找 prices[j] - prices[i] 的最大值（j > i）。

代码

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;
        }
    }
    return maxProfit;
}

复杂度

• 时间：O(n) — 遍历一次
• 空间：O(1) — 两个变量

边界条件

• 数组为空或只有一天：无法完成一次买卖，maxProfit 保持初始值 0（循环体最多执行一次或零次，不会误更新）。
• 价格单调递减（如 [7,6,4,3,1]）：每天都刷新 minPrice，maxProfit 始终为 0，代表不交易是最优解。
• 价格单调递增（如 [1,2,3,4,5]）：minPrice 恒为第一天，maxProfit 在最后一天达到全局最大。

变式

• 允许多次交易（LeetCode 122 题）：只要今天比昨天贵就”买卖一次”，把每一段上涨区间的利润都累加起来，是贪心而不是这里的”单次最优”。
• 最多两次交易（LeetCode 123 题）：需要维护四个状态（第一次买入/卖出、第二次买入/卖出的最大利润），是本题状态机思路的推广，属于动态规划范畴。
• 含冷冻期/手续费：在多次交易的基础上加状态转移的额外约束，本质仍是这套”维护若干个滚动最优值”的框架。

易错点

• 不能理解成”求最大差值不管顺序”：必须保证卖出日期在买入日期之后，minPrice 只能取当前位置之前出现过的最低价，代码里正是先判断 price < minPrice 更新，再看差值，天然保证了顺序。
• 初始 minPrice 要设成 Integer.MAX_VALUE（或第一个价格），否则第一天的价格可能被误判成”卖出价”而不是”最低买入价”。

面试追问

• 只交易一次和可以交易多次，为什么解法差异这么大？ 单次交易只需要维护”历史最低点”这一个信息，是贪心的特例；多次交易需要考虑”什么时候该卖出去锁定利润、什么时候该继续持有”，变成了需要状态转移的动态规划问题。
• 如果要求返回具体是哪两天买卖，而不只是利润数字？ 在更新 maxProfit 的同时记录当时的买入下标（minPrice 对应的下标）和卖出下标即可，不影响时间复杂度。

关联题

• 同套路：53. 最大子数组和 —— 相邻差价数组的最大子数组和即本题，“维护历史最低买入价”是其等价形式
• 进阶：122（可多次交易 → 贪心收集正差价）→ 123/188（限 k 次 → 状态机 DP）→ 309（含冷冻期）
• 知识点：股票系列是状态机 DP 的教科书，见动态规划