题目描述
给定一个整数数组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) | ⭐⭐⭐ | 直观理解价格波段 |
关键点：
贪心算法是本题的最优解法
动态规划是解决股票问题的通用框架
理解贪心算法的正确性：多次买卖的总利润等于所有上升波段差值的和
在面试中，建议先给出贪心解法，然后如果时间允许或面试官要求，再讨论动态规划解法以展示你的全面性。
