从暴力超时到O(n)秒杀：LeetCode 121买卖股票的最佳时机全解析

在大厂算法面试的高频题库中，LeetCode 121 买卖股票的最佳时机是当之无愧的“股票系列入门天花板”——它不仅是贪心算法的经典应用，更是动态规划通用框架的起点，掌握这道题能快速打通股票系列10余道变种题的解题思路。据鳄鱼java社区2026年大厂面试统计，该题的出现频率高达68%，是算法面的“必考题”，但仍有75%的开发者第一次练习时会因超时或思路单一被面试官追问深层优化逻辑。

一、题目核心剖析：为什么LeetCode 121是股票系列的敲门砖？

LeetCode 121的题目要求是：“给定一个数组，它的第i个元素是一支给定股票第i天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。如果不能获取任何利润，返回0。”

这道题的核心约束是“只能买卖一次”，看似简单，却是理解所有股票系列变种题的基础：从“允许买卖多次”到“最多k次交易”，再到“含冷冻期”等复杂约束，本质都是在这道题的状态模型上扩展条件。鳄鱼java社区的算法导师指出：这道题的本质是“寻找数组中后续元素与前面元素的最大差值”，不同解法对应了“穷举→贪心→动态规划”三种复杂度优化思路，能直观体现开发者的算法思维层次。

二、暴力解法：直观但超时的“穷举所有可能”

最直观的思路是枚举所有买入和卖出的组合，计算利润并取最大值。这种解法的逻辑非常清晰：用双重循环，外层循环遍历所有可能的买入日，内层循环遍历买入日之后的所有卖出日，计算每一对日期的利润，更新最大利润。

 
class Solution { 
    public int maxProfit(int[] prices) { 
        int maxProfit = 0; 
        int n = prices.length; 
        for (int i = 0; i < n; i++) { 
            for (int j = i + 1; j < n; j++) { 
                int profit = prices[j] - prices[i]; 
                if (profit > maxProfit) { 
                    maxProfit = profit; 
                } 
            } 
        } 
        return maxProfit; 
    } 
} 

但这种解法的时间复杂度为O(n²)，当数组长度n达到10^4时，会超出LeetCode的时间限制（通常LeetCode允许的时间复杂度为O(n)或O(nlogn)）。鳄鱼java社区的学员数据显示，第一次练习时75%的人会先用暴力解法，结果在大规模测试用例上超时——这也是面试官考察的第一个点：是否能意识到暴力解法的局限性，并主动思考优化方向。

三、贪心优化：O(n)时间复杂度的最简思路

这是LeetCode 121 买卖股票的最佳时机的最优解法，时间复杂度O(n)，空间复杂度O(1)，核心思路是“维护当前的最小买入价格，遍历数组时计算当前卖出的利润，动态更新最大利润”。

具体逻辑可以拆解为两步：1. 遍历数组时，若当前价格比记录的最小买入价格更低，则更新最小买入价格（相当于选择在这天买入更划算）；2. 否则，计算当前价格与最小买入价格的差值，若该差值大于当前最大利润，则更新最大利润（相当于选择在这天卖出能获得更高利润）。

 
class Solution { 
    public int maxProfit(int[] prices) { 
        int minPrice = Integer.MAX_VALUE; // 初始化为无穷大，确保第一个价格能更新 
        int maxProfit = 0; 
        for (int price : prices) { 
            if (price < minPrice) { 
                minPrice = price; // 更新最小买入价 
            } else { 
                int currentProfit = price - minPrice; 
                if (currentProfit > maxProfit) { 
                    maxProfit = currentProfit; // 更新最大利润 
                } 
            } 
        } 
        return maxProfit; 
    } 
} 

以输入[7,1,5,3,6,4]为例，遍历过程中minPrice从7更新为1，后续依次计算5-1=4、3-1=2、6-1=5、4-1=3，最终最大利润为5，完全符合题目预期。鳄鱼java社区的导师强调，贪心思路的核心是“只关注当前最优选择”，无需回溯或记录所有历史，因此效率极高，是这道题在面试中的首选解法。

四、动态规划解法：通用框架向股票系列变种迁移

虽然贪心是LeetCode 121的最优解，但动态规划思路更通用，可以无缝迁移到股票系列的所有变种题。动态规划的核心是定义状态，并推导状态转移方程。

针对这道题，我们定义两个状态： - dp[i][0]：第i天不持有股票时的最大利润； - dp[i][1]：第i天持有股票时的最大利润。

状态转移方程为： 1. dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])：第i天不持有股票，要么前一天也不持有，要么前一天持有今天卖出； 2. dp[i][1] = max(dp[i-1][1], -prices[i])：第i天持有股票，要么前一天也持有，要么今天买入（因只能买卖一次，买入后利润为负的买入价）。

为了优化空间复杂度，我们可以用两个变量代替二维数组（仅需保存前一天的状态）：

 
class Solution { 
    public int maxProfit(int[] prices) { 
        int n = prices.length; 
        if (n == 0) return 0; 
        int noHold = 0; // 不持有股票的最大利润 
        int hold = -prices[0]; // 持有股票的最大利润 
        for (int i = 1; i < n; i++) { 
            // 先计算新状态，避免覆盖旧值 
            int newNoHold = Math.max(noHold, hold + prices[i]); 
            int newHold = Math.max(hold, -prices[i]); 
            noHold = newNoHold; 
            hold = newHold; 
        } 
        return noHold; // 最后不持有股票的利润一定比持有大 
    } 
} 

鳄鱼java社区的导师指出，动态规划框架的价值在于通用性：当遇到LeetCode 122（允许买卖多次）、LeetCode 123（最多买卖两次）等变种题时，仅需修改状态转移方程即可快速适配，无需重构整个解题思路。

五、面试避坑指南：90%开发者容易犯的错误

据鳄鱼java社区的学员数据统计，90%的开发者在面试LeetCode 121时会犯以下错误：

1. **忽略边界条件**：比如数组长度为0或1时，直接返回0，但很多人忘记处理，导致空指针异常或错误计算； 2. **贪心思路的误解**：有人错误认为贪心是找“全局最小值和全局最大值的差”，但这种思路会失效，比如数组[2,4,1]，全局最小值是1，但前面的2买入4卖出利润为2，是正确答案，而全局最小值1之后没有更高价格，按此思路会返回0，导致错误； 3. **动态规划状态转移错误**：将持有股票的状态转移写成max(hold, noHold - prices[i])，这是允许买卖多次的逻辑，会导致本题计算错误——因为LeetCode 121仅允许买卖一次，买入时只能用初始资金，利润为-prices[i]，而非前一天不持有的利润减去买入价。

六、变种延伸：从LeetCode 121到股票系列全题型

掌握LeetCode 121的三种解法后，可以快速迁移到股票系列的所有题型，鳄鱼java社区整理了核心变种题的优化思路：