LC121. 买卖股票的最佳时机

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2： 输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。 提示： 1 <= prices.length <= 10(5) 0 <= prices[i] <= 10(4)

题目解析

题目在说什么

这道题其实就是在模拟一个最简单的炒股场景：你只有一次买入和一次卖出的机会。给你一个数组，比如 [7,1,5,3,6,4]，每个数字代表某一天股票的价格。你要选择一天买入（比如第2天价格1元），再选择未来某一天卖出（比如第5天价格6元），赚取差价（6-1=5元）。如果股票一直在跌（比如 [7,6,4,3,1]），那就不做任何交易，利润为0。

简单说：找出一对“先买后卖”的价格，让卖出价减去买入价的差值最大。

思路是怎么来的

想象你是一个小商贩，每天只能决定“买进”或“卖出”一次。你希望最后口袋里的钱最多。这个问题其实可以拆成两个小问题：

1. 今天手里有没有股票？ 如果有，你可以选择“继续持有”或“今天卖掉”；如果没有，你可以选择“继续空仓”或“今天买入”。 2. 你最多能交易几次？ 题目限制只能交易一次（一次买入+一次卖出），所以一旦卖掉了，就不能再买了。

我们可以用“状态”来描述每天结束时的情况。比如：

• 状态A：今天结束时，手里没有股票，且已经完成过0次交易（也就是什么都没做）。
• 状态B：今天结束时，手里没有股票，且已经完成过1次交易（也就是已经卖出过一次）。
• 状态C：今天结束时，手里有1股股票，且已经完成过1次交易（也就是买入过一次，还没卖）。

但注意，题目只允许一次交易，所以“持有股票”的状态只可能发生在“已经买入但还没卖出”时。而“不持有股票”的状态有两种：要么还没买过，要么已经卖掉了。

参考代码用了一个三维数组 dp[i][k][b] 来记录这些状态：

• i：第几天（从0开始）。
• k：最多交易次数（这里固定为1）。
• b：是否持有股票（0=不持有，1=持有）。

比如 dp[2][1][0] 表示：第2天结束时，最多交易1次，且手里没有股票时的最大利润。

代码逐步拆解

我们一行一行来看参考代码在做什么。

1. 初始化（第0天）

int length = prices.length;
int[][][] dp = new int[length][2][2];

这里创建了一个三维数组。length 是天数，2 是交易次数（0和1），2 是是否持有股票（0和1）。注意：交易次数k这里只用了1，但数组大小是2（索引0和1），因为我们要用到 k=0 的状态（表示还没交易过）。

dp[0][0][0] = 0;   // 第0天，没交易过，没股票，利润0
dp[0][1][0] = 0;   // 第0天，最多交易1次，没股票，利润0（实际上还没交易）
dp[0][1][1] = -prices[0]; // 第0天，最多交易1次，持有股票，说明买入了，利润是 -价格

为什么持有股票时利润是负数？因为买入花了钱，相当于从口袋里掏出了 prices[0] 元，所以利润是负的。

2. 状态转移（从第1天开始）

从第1天到第 length-1 天，每天更新两个状态：

状态1：今天不持有股票（`dp[i][1][0]`）

有两种可能：

• 昨天就不持有，今天也没操作：dp[i-1][1][0]
• 昨天持有，今天卖掉了：dp[i-1][1][1] + prices[i]（卖出得到现金，所以利润增加）

取两者中较大的那个，因为我们要最大利润。

状态2：今天持有股票（`dp[i][1][1]`）

也有两种可能：

• 昨天就持有，今天没操作：dp[i-1][1][1]
• 昨天不持有且没交易过（dp[i-1][0][0]），今天买入：dp[i-1][0][0] - prices[i]（买入花钱，利润减少）