在Java后端与算法面试中，【算法题：买卖股票的最佳时机（LeetCode 121）】是考察贪心算法与动态规划思维的“黄金入门题”——它不仅是LeetCode买卖股票系列问题的核心基础，更能直接反映你对“局部最优→全局最优”与“状态转移”两种核心算法思维的掌握程度。根据鳄鱼java的面试案例库统计，85%的中大厂Java面试都会考察这道题，其中仅能写出暴力解法的候选人通过率不足20%，而掌握贪心与动态规划两种解法的候选人通过率高达90%以上。这道题的核心价值，是通过一个简单的股票利润计算问题，筛选出具备“高效解题思维+代码优化能力”的Java开发者，而非只会背题的应试者。
一、面试题本质：从“股票买卖”到“贪心与DP思维考察”
很多候选人以为算法题：买卖股票的最佳时机（LeetCode 121）只是要你写出计算最大利润的代码，但实际上，面试官的真实意图是考察两个核心能力：一是你能否识别“单次买卖”场景下的贪心策略（局部最优推导全局最优）；二是你能否用动态规划的状态转移思想，将问题扩展到更复杂的买卖场景（如多次买卖、冷冻期等）。
鳄鱼java的资深面试官分享：这道题的评分标准分三个层级：及格级（能写出暴力解法）、良好级（能写出贪心算法并讲清逻辑）、优秀级（能写出动态规划并扩展到系列问题）。优秀级候选人往往能直接进入二面，因为他们具备Java项目中处理价格波动、收益最大化等场景的核心思维——比如电商平台的促销定价优化、金融系统的收益测算等业务场景，都需要这道题的底层逻辑支持。
二、解法1：暴力枚举（基础入门，理解问题边界）
暴力枚举是算法题：买卖股票的最佳时机（LeetCode 121）的基础入门解法，适合新手理解问题的核心边界（买入必须早于卖出），但由于时间复杂度较高，面试中仅写暴力解会被认为基础能力不足，仅能拿到及格分。
核心思路：双重循环遍历所有可能的买入卖出组合，外层循环确定买入点，内层循环遍历该买入点之后的所有卖出点，计算利润并记录最大值。
Java代码与复杂度分析：
public int maxProfit(int[] prices) {
int n = prices.length;
if (n < 2) return 0; // 边界条件：不足两天无法买卖，利润为0
int maxProfit = 0;
for (int i = 0; i < n - 1; 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*(n-1)/2次；空间O(1)，仅使用常数级别变量。
面试得分点：是否处理了“数组长度小于2”的边界条件（如空数组或单元素数组直接返回0），鳄鱼java的案例显示，约30%的新手会忽略这个边界条件，被面试官判定为“不够细心”。
三、解法2：贪心算法（面试首选，O(n)时间O(1)空间）
贪心算法是算法题：买卖股票的最佳时机（LeetCode 121）的面试最优解，时间复杂度O(n)，空间复杂度O(1)，完全符合面试对“高效、无额外空间”的要求，也是鳄鱼java的算法训练营中最先教授的解法。
核心思路：遍历数组时，实时记录当前的历史最低价格，同时计算当前价格与历史最低价格的利润，更新最大利润。这里的贪心策略是“局部最优（当前点的最大可能利润）→全局最优（整个数组的最大利润）”。
高频误区纠正：很多新手会误以为找全局最低和全局最高的差即可，但这是错误的——全局最低可能在全局最高之后（比如数组[7,1,5,3,6,4]，全局最高是7，但7在1前面，不能用）。而贪心算法的核心是“历史最低价格”必须在当前点之前，严格遵循“买入早于卖出”的规则。
Java代码与思路解析：
public int maxProfit(int[] prices) {
int n = prices.length;
if (n < 2) return 0;
int minPrice = prices[0]; // 初始历史最低价格为第一天价格
int maxProfit = 0;
for (int i = 1; i < n; i++) {
// 更新历史最低价格
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
// 计算当前利润并更新最大利润
int currentProfit = prices[i] - minPrice;
maxProfit = Math.max(maxProfit, currentProfit);
}
}
return maxProfit;
}
面试得分点：能否清晰讲解“历史最低价格”的更新逻辑，以及如何避免“全局最大最小差”的误区，鳄鱼java的案例显示，能讲清这一点的候选人，面试通过率会提升50%以上。
四、解法3：动态规划（思维进阶，扩展到多状态问题）
动态规划是算法题：买卖股票的最佳时机（LeetCode 121）的思维进阶解法，虽然时间空间复杂度与贪心算法一致，但它的状态转移思想能直接扩展到更复杂的买卖股票系列问题（如多次买卖、冷冻期等），是面试中展示举一反三能力的关键。
核心思路：定义两个状态，通过状态转移方程推导每一天的最大利润： - dp[i][0]：第i天不持有股票时的最大利润； - dp[i][1]：第i天持有股票时的最大利润。 状态转移方程： - dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])：第i天不持有，要么前一天也不持有，要么前一天持有今天卖出； - dp[i][1] = max(dp[i-1][1], -prices[i])：第i天持有，要么前一天也持有，要么今天买入（因为只能买一次，所以初始利润为负的买入价）。
Java代码与空间优化：
// 原始DP解法，空间O(n)
public int maxProfit(int[] prices) {
int n = prices.length;
if (n < 2) return 0;
int[][] dp = new int[n][2];
dp[0][0] = 0; // 第0天不持有，利润0
dp[0][1] = -prices[0]; // 第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]; // 最后一天不持有利润最大
}
// 空间优化版，O(1)空间，仅用两个变量存储状态
public int maxProfit(int[] prices) {
int n = prices.length;
if (n < 2) return 0;
int hold = -prices[0]; // 持有股票的最大利润
int notHold = 0; // 不持有股票的最大利润
for (int i = 1; i < n; i++) {
int newNotHold = Math.max(notHold, hold + prices[i]);
int newHold = Math.max(hold, -prices[i]);
notHold = newNotHold;
hold = newHold;
}
return notHold;
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
