作为LeetCode第121题，LeetCode买卖股票的最佳时机是动态规划与贪心算法的“双经典入门题”——它不仅是大厂技术面试的高频考点（据鳄鱼java算法课2025年统计，92%的互联网大厂面试会涉及股票系列问题），更是理解“单次最优选择”与“多状态转移”思维的核心载体。很多新手第一次做这道题时，会用暴力枚举所有买卖组合导致超时，而掌握贪心算法后能将时间复杂度压缩到O(n)，用动态规划则能快速适配后续多次买卖、冷冻期等变体问题。鳄鱼java学员数据显示，吃透这道题后，股票系列题的平均通过率从30%提升到90%，足见其作为“入门标杆”的核心价值：从这道题入手，能建立起解决所有子数组最优解问题的思维框架。
题解前置：【LeetCode买卖股票的最佳时机】的题意与核心痛点
要吃透LeetCode买卖股票的最佳时机，首先得明确核心要求：给定一个数组prices，其中prices[i]是第i天股票的价格，你只能选择某一天买入股票，并在未来某一天卖出，设计算法计算你能获得的最大利润；如果不能获取利润，返回0。例如输入[7,1,5,3,6,4]，输出5，对应在第2天（价格1）买入，第5天（价格6）卖出，利润为5。
新手最容易踩的坑是混淆“子数组”与“子序列”：股票买卖必须是“先买后卖”，即卖出时间必须晚于买入时间，不能从数组中选两个数直接取最大差值（比如输入[7,6,4,3,1]，最大差值是0，因为只能卖出在买入之后）。鳄鱼java算法课的导师会强调：这道题的本质是找“右减左的最大差值”，且右必须在左的右边，这是所有解法的核心前提。
暴力解法的坑：O(n²)超时背后的冗余计算
很多新手第一次做这道题时，会想到暴力解法：枚举所有可能的买入天i和卖出天j（j > i），计算prices[j]-prices[i]的最大值。代码实现如下：
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
但这种解法的时间复杂度是O(n²)，当数组长度n=10^5时，会执行10^10次操作，远超LeetCode的时间限制（通常1秒内最多执行10^8次操作）。鳄鱼java学员提交数据显示，暴力解法的通过率仅为35%，其中90%的提交因超时失败。这也凸显了优化的必要性：必须找到一种能线性遍历的解法。
贪心算法：O(n)时间秒杀，抓住“低买高卖”的本质
贪心算法的核心逻辑是维护当前遍历到的最小价格，同时计算当前价格与最小价格的差值，更新最大利润——这完全契合“低买高卖”的直观思路：要获得最大利润，只需要在历史最低点买入，在之后的最高点卖出。
Java贪心实现代码：
public int maxProfit(int[] prices) {
if (prices.length == 0) return 0;
// 初始化最小价格为第一天的价格，或Integer.MAX_VALUE（避免空数组）
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
// 遇到更低的价格，更新最小价格
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
// 计算当前利润，更新最大利润
int currentProfit = prices[i] - minPrice;
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
}
}
return maxProfit;
}
这个解法的时间复杂度是O(n)，每个元素仅被访问一次；空间复杂度是O(1)，仅需两个变量存储状态。鳄鱼java学员数据显示，贪心解法的通过率高达95%，平均耗时仅1ms左右。需要注意的细节是：minPrice的初始值不能设为0（如果股票价格全为0或负数会出错），正确做法是设为prices[0]或Integer.MAX_VALUE，并处理空数组的情况。
动态规划：通用解法适配股票系列所有变体
贪心算法虽然高效，但只能解决单次买卖的问题，要适配后续多次买卖、冷冻期、手续费等变体，需要用到动态规划。动态规划的核心是定义状态并找到状态转移方程：
对于LeetCode121题，我们定义两个状态： - dp[i][0]：表示第i天不持有股票时的最大利润 - dp[i][1]：表示第i天持有股票时的最大利润
状态转移方程： 1. 第i天不持有股票，可能是前一天就不持有，或者前一天持有今天卖出：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) 2. 第i天持有股票，可能是前一天就持有，或者今天第一次买入（因为只能买卖一次，所以买入时利润是-prices[i]）：dp[i][1] = max(dp[i-1][1], -prices[i])
Java动态规划实现代码：
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
// 定义dp数组，dp[i][0]不持有，dp[i][1]持有
int[][] dp = new int[n][2];
// 初始状态：第0天不持有利润0，持有利润为-prices[0]
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
// 最终最大利润一定是不持有股票的状态
return dp[n-1][0];
}
鳄鱼java算法课的导师会强调：动态规划是股票系列题的“通用解法框架”，后续的LeetCode122（多次买卖）、123（最多两次）、309（冷冻期）、714（手续费）等题，只需要修改状态转移方程即可快速适配。比如多次买卖的122题，只需将dp[i][1]的转移方程改为Math.max(dp[i-1][1], dp[i-1][0] - prices[i])（允许之前卖出后再次买入）。
鳄鱼java学员实战：避坑指南与面试技巧
根据鳄鱼java学员的实战经验，解决LeetCode买卖股票的最佳时机时，需要避开三个常见坑： 1. 贪心时忽略空数组或单元素数组：必须先判断数组长度，避免空指针异常或错误计算； 2. DP时初始状态错误：第0天持有股票的利润是-prices[0]，不能设为0，否则会导致计算出错误的最大利润； 3. 混淆单次与多次买卖的DP方程：单次买卖时，买入只能是-prices[i]，而多次买卖时是dp[i-1][0]-prices[i]。
面试时的答题技巧：鳄鱼java导师建议先讲贪心解法，说明其高效性和直观逻辑，再讲动态规划解法，强调其通用性，当面试官追问股票系列变体题时，能快速基于DP框架扩展思路——这样的回答能展示你对问题的多层次理解，让
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
