LeetCode 121. 买卖股票的最佳时机

约 4 分钟
文章信息 26 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 需复习 200-500 字节跳动 微软 美团 阿里巴巴 快手 腾讯 百度 滴滴 京东 华为 拼多多 网易 小米 商汤 亚马逊 虾皮 携程 小红书 LeetCode 热题 100 面试经典 150 题
标签
数组 动态规划 股票买卖问题
目录

题目描述

✅ 121. 买卖股票的最佳时机

image-20250510002759914

题意分析

prices[i] 是第 i 天的股价，要在这串价格上选一次买入和一次卖出，使利润最大。题面给出的约束只有两条，但两条都必须抠清楚。

第一条是只能买卖一次：不允许「低买高卖再低买高卖」地反复吃波段，整段价格序列上只挑一对下标。这一点把它和后面的股票系列题彻底区分开了——那些题的答案通常是把所有上涨区间累加，而本题的答案只能来自一对下标。

第二条是卖出日必须严格晚于买入日：不能在买入的当天就卖出，更不能拿后面的低价去解释前面的高价。于是整道题可以严格改写成一句话：求满足 j > i 的 prices[j] - prices[i] 的最大值。这个改写很关键，因为它把「买卖」这种带时间语义的描述，变成了纯粹的「下标对 + 顺序约束」，后面所有推导都建立在这句话上。

还有一条藏在返回值说明里：如果不存在任何盈利机会，返回 0。它的真实含义是「允许不交易」，也就是答案的下界被钉死在 0，最终结果等于 $\max(0, \max_{j>i}(prices[j] - prices[i]))$。这一点值得和 53 题最大子数组和对照着记：53 题要求子数组必须非空，所以全是负数时答案是那个最大的负数；本题允许「空方案」，所以全程下跌时答案是 0，而不是那个最小的亏损。同一类扫描题，答案初值取 0 还是取第一个元素，分水岭就在这里。

两个边界值得先想清楚。价格单调递减时（例如 [7,6,4,3,1]），任何合法的下标对都给出负数，答案是 0；数组只有一天时（例如 [5]），连一对合法下标都凑不出来，答案同样是 0。

解法：一次遍历维护历史最低价

核心思路

从左到右扫描。把当前价格视为卖出价时，最优买入价就是此前出现过的最低价；用两者之差更新最大利润，再更新最低价。最大利润初始为 0，自然覆盖不交易的情况。

解题步骤

  • 初始化历史最低价 minPrice = prices[0]，最大利润 maxProfit = 0。
  • 从第二天开始，计算当天卖出可得的利润，并更新 maxProfit。
  • 将当天价格纳入历史最低价，扫描结束后返回 maxProfit。

代码实现

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }
        return maxProfit;
    }
}

func maxProfit(prices []int) int {
    minPrice, maxProfit := prices[0], 0

    for _, price := range prices[1:] {
        if profit := price - minPrice; profit > maxProfit {
            maxProfit = profit
        }
        if price < minPrice {
            minPrice = price
        }
    }
    return maxProfit
}

复杂度分析

  • 时间复杂度：$O(n)$，每个价格只处理一次。
  • 空间复杂度：$O(1)$，只使用两个变量。

关键点总结

  • 固定卖出日后，只需维护它之前的最低价格，无需枚举所有买卖组合。
  • 先计算利润、再更新最低价，买入日始终早于卖出日。
  • 利润初始为 0；全程下跌时不交易。

易错点总结

  • 直接用全局最高价减全局最低价，可能违反先买后卖的顺序。
  • 将 minPrice 初始化为 0，会把不存在的 0 元买入价算进答案。
  • 累加每段上涨利润解决的是可多次交易的 122 题，不是本题。

相似题目

题目 难度 考察点
122. 买卖股票的最佳时机 II 中等 交易次数不限，答案变成累加所有上涨区间，而非只取一对下标
123. 买卖股票的最佳时机 III 困难 最多两次交易，需要按「第几次买入/卖出」拆成四个状态
188. 买卖股票的最佳时机 IV 困难 交易次数上限是入参 k，状态要多加一维交易次数
309. 买卖股票的最佳时机含冷冻期 中等 卖出后一天不能买入，买入转移只能从 i-2 天的空仓状态来
714. 买卖股票的最佳时机含手续费 中等 每笔交易额外扣手续费，微小波动不再值得吃，贪心边界随之改变
剑指 Offer 63. 股票的最大利润 中等 与本题完全同源的单次交易问题，可直接套用维护历史最低价的写法
53. 最大子数组和 中等 同为一次扫描维护前缀极值，但子数组必须非空，全负时答案是负数而不是 0