当前位置：首页 > news >正文

LeetCode 122. 买卖股票的最佳时机 II - 推荐贪心

news 2026/5/12 20:56:54

题目描述

给定一个整数数组prices，其中prices[i]表示某支股票第i天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而，你可以在同一天多次买卖该股票，但要确保你持有的股票不超过一股。

返回你能获得的最大利润。

示例 1：

text

输入：prices = [7,1,5,3,6,4] 输出：7 解释：在第 2 天买入，第 3 天卖出，利润 5-1=4 在第 4 天买入，第 5 天卖出，利润 6-3=3 总利润 4+3=7

示例 2：

text

输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天买入，第 5 天卖出，利润 5-1=4 注意你不能在第 1 天和第 2 天连续买入股票

示例 3：

text

输入：prices = [7,6,4,3,1] 输出：0 解释：没有交易完成，最大利润为 0

解法一：贪心算法（面试推荐⭐）

核心思想

只要今天的价格比昨天高，就昨天买入今天卖出。虽然这看起来像是频繁交易，但数学上等价于在价格上升波段的最低点买入、最高点卖出。

算法步骤

从第二天开始遍历价格数组
计算当天与前一天的价格差
如果价格差为正（当天价格 > 前一天价格），则累加到总利润中
返回总利润

代码实现

java

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

复杂度分析

时间复杂度：O(n)，只需遍历一次数组
空间复杂度：O(1)，只使用了常数级别的额外空间

为什么这是正确的？

考虑价格序列 [1, 3, 5]：

贪心算法：第1天买入，第2天卖出（利润2），第2天买入，第3天卖出（利润2），总利润4
最优策略：第1天买入，第3天卖出，总利润4
两种策略结果相同，因为 (5-1) = (3-1) + (5-3)

解法二：动态规划（通用解法）

核心思想

定义两个状态：

dp[i][0]：第i天结束时，不持有股票的最大利润
dp[i][1]：第i天结束时，持有股票的最大利润

状态转移方程

text

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) // 保持空仓或卖出 dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) // 保持持有或买入

代码实现

java

class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[][] dp = new int[n][2]; 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], dp[i-1][0] - prices[i]); } return dp[n-1][0]; // 最后一天不持有股票时利润最大 } }

空间优化版本

java

class Solution { public int maxProfit(int[] prices) { int hold = -prices[0]; // 持有股票的最大利润 int notHold = 0; // 不持有股票的最大利润 for (int i = 1; i < prices.length; i++) { int prevHold = hold; hold = Math.max(hold, notHold - prices[i]); notHold = Math.max(notHold, prevHold + prices[i]); } return notHold; } }

复杂度分析

时间复杂度：O(n)
空间复杂度：未优化版本 O(n)，优化版本 O(1)

解法三：峰谷法（直观理解）

核心思想

寻找价格序列中的连续上升波段，在每个波段的谷底买入、峰顶卖出。

算法步骤

初始化利润为0，指针i从0开始
寻找价格低谷（价格开始上升的点）
寻找价格高峰（价格开始下降的点）
计算峰谷差值并累加到利润
重复直到遍历完整个数组

代码实现

java

class Solution { public int maxProfit(int[] prices) { int profit = 0; int i = 0; int n = prices.length; while (i < n - 1) { // 寻找低谷（价格停止下降的点） while (i < n - 1 && prices[i] >= prices[i + 1]) { i++; } int valley = prices[i]; // 寻找高峰（价格停止上升的点） while (i < n - 1 && prices[i] <= prices[i + 1]) { i++; } int peak = prices[i]; profit += peak - valley; } return profit; } }

复杂度分析

时间复杂度：O(n)，每个元素最多被访问两次
空间复杂度：O(1)

面试推荐写法

首推：贪心算法 ✅

原因：

代码最简洁（仅5-7行）
时间空间复杂度最优
容易理解和解释
面试中快速写出并分析正确性

面试回答模板：

"这道题可以使用贪心算法解决。核心思想是：只要第二天的价格比第一天高，就把这个差价算作利润。虽然看起来像是频繁交易，但实际上等价于在价格上升波段中一直持有股票。算法的时间复杂度是O(n)，空间复杂度是O(1)。"

备选：动态规划

如果面试官要求更通用的解法，或者后续问题扩展（如含交易费、冷冻期等），可以使用动态规划解法。

扩展思考

如果加上交易手续费？

每次卖出时扣除手续费：

java

public int maxProfit(int[] prices, int fee) { int hold = -prices[0]; int notHold = 0; for (int i = 1; i < prices.length; i++) { hold = Math.max(hold, notHold - prices[i]); notHold = Math.max(notHold, hold + prices[i] - fee); } return notHold; }

如果加上冷冻期？

卖出后需要等待一天才能买入：

java

public int maxProfit(int[] prices) { if (prices.length <= 1) return 0; int hold = -prices[0]; int notHold = 0; int coolDown = 0; // 冷冻期 for (int i = 1; i < prices.length; i++) { int prevHold = hold; hold = Math.max(hold, coolDown - prices[i]); coolDown = notHold; notHold = Math.max(notHold, prevHold + prices[i]); } return notHold; }

总结

解法	时间复杂度	空间复杂度	推荐指数	适用场景
贪心算法	O(n)	O(1)	⭐⭐⭐⭐⭐	面试首选，代码简洁高效
动态规划	O(n)	O(1)~O(n)	⭐⭐⭐⭐	通用性强，可扩展
峰谷法	O(n)	O(1)	⭐⭐⭐	直观理解价格波段