企业官网建设流程全解析

标题里的“得”十有八九是手误，正确写法应该是“买卖股票的最佳时期”。这道题我在各大在线题库都见过，也是很多刷题清单上绕不开的一道经典。题目本身不难理解：给一个数组，第 i 个元素表示某只股票第 i 天的价格，你只能选择某一天买入、之后的某一天卖出，求最大利润；如果怎么买卖都赚不到钱，就返回 0。我第一次做的时候觉得这就是找个最大值减最小值，结果连续两次提交都在“全局最大价出现在全局最小价之前”这种例子上翻车。后来花了一下午把它的几个变体全部刷完，才意识到这道题背后其实藏着贪心、状态机 DP、二维 DP 一整条算法主线。这篇文章就按我当时的思考顺序来写，适合正在刷题、准备技术面试，或者想系统搞懂动态规划状态机的朋友。

1. 先把这个经典问题读透：什么才算“最佳时期”

1.1 题目到底在问什么

题目通常会这样描述：给定一个数组prices，其中prices[i]表示股票在第 i 天的价格。你只能在某一天买入，并在之后的某一天卖出，求能获得的最大利润。

看两个标准示例：

• 输入[7,1,5,3,6,4]，输出5。对应操作是第 2 天（价格 1）买入，第 5 天（价格 6）卖出，利润6 - 1 = 5。
• 输入[7,6,4,3,1]，输出0。价格一路下跌，任何买入都会亏，所以选择不交易，利润为 0。

这里有几个容易忽略的限定条件，做题前必须先明确：

1. 只能完成一笔交易，也就是一次买入加一次卖出。买完再买、卖完再卖都不允许。
2. 卖出日必须在买入日之后，严格大于，不能同一天买同一天卖。
3. 可以不交易，如果所有可能的买卖都是亏损，答案是 0 而不是负数。

很多人会下意识把它当成“数组最大值减最小值”，这恰恰是最容易出错的地方。因为时间顺序是有约束的，最大值可能出现在最小值之前，那这笔“交易”在时间上根本不成立。比如[5, 1, 4]，全局最大是 5，全局最小是 1，直接相减得到 4，但 5 在第 1 天，1 在第 2 天，你不可能先以 5 买入再以 1 卖出。正确答案是第 2 天买、第 3 天卖，利润 3。

1.2 为什么这道题值得反复做

作为一个刷题老手，我可以说这道题是“性价比”极高的题目之一。代码量非常小，最优解只有十几行，但它考察的优化思维非常典型：从暴力枚举到发现重复计算，再到用单个变量维护中间结果。这个过程几乎是所有“双循环改单循环”类题目的标准范本。

更关键的是它有一整个变体家族：

• 允许无限次交易，只要卖完才能再买；
• 卖出后必须冷冻一天才能再买；
• 每次交易要扣手续费；
• 最多只能交易 k 次。

每一个变体都对应一种典型解法，从贪心到状态机 DP 再到二维 DP。也就是说，认真吃透这一道题，等于同时复习了算法面试里几个最重要的思想。这也是为什么很多刷题清单都会把它放在前几十题的位置上，作为入门到进阶的衔接题。

2. 从暴力枚举到一趟扫描：最优解是怎么“长”出来的

2.1 暴力解：把每一对买卖都算一遍

拿到题目最直接的想法就是枚举：遍历每一个可能的买入日 i，再遍历所有在它之后的日子 j，计算prices[j] - prices[i]，不断更新最大值。

def max_profit_brutal(prices): n = len(prices) best = 0 for i in range(n): for j in range(i + 1, n): profit = prices[j] - prices[i] if profit > best: best = profit return best

这段代码逻辑完全正确，但时间复杂度是 O(n²)。刷题平台给的数据范围通常是 n 最大到 10 万量级，O(n²) 意味着要做约 10^10 次运算，直接超时。暴力解的意义只在于帮助我们确认问题语义，真正要追求的是线性时间解法。

2.2 关键观察：每个卖出日的最优买入价就是历史最低价

暴力解慢在哪里？我们来看它的重复计算。对于固定的卖出日 j，最优的买入日一定是在[0, j-1]区间内价格最低的那一天。也就是说，对每个 j，我们要知道的是min(prices[0..j-1])。

但双重循环里，内层循环对不同的 j 重复扫描了大量公共前缀，这个最小值被反复重新计算。如果我们在从左到右遍历的过程中，实时维护“到目前为止的最低价格”，那么每个卖出日只需要一次减法就能得到最优利润。

def max_profit(prices): min_price = float('inf') best = 0 for price in prices: if price < min_price: min_price = price elif price - min_price > best: best = price - min_price return best

用[7,1,5,3,6,4]手动走一遍：

• 第 1 天价格 7：最低价更新为 7，利润 0；
• 第 2 天价格 1：最低价更新为 1，利润 0；
• 第 3 天价格 5：利润 4，best 变为 4；
• 第 4 天价格 3：利润 2，不更新；
• 第 5 天价格 6：利润 5，best 变为 5；
• 第 6 天价格 4：利润 3，不更新。

最终得到 5。这个解法的本质是：把“选买入日”的问题转化为“维护历史最低价”的问题，让每个卖出日都能用 O(1) 时间算出最优买入结果。时间复杂度 O(n)，空间复杂度 O(1)。

2.3 动态规划的视角：两个状态搞定

如果觉得上面的思路太“技巧化”，可以换一个更通用的状态机视角。我们把每天结束时的持仓状态分成两种：

• hold：手里持有股票，当前收益是买入花掉的钱，即某种意义上的“负收益”；
• sold：手里没有股票，当前已经落袋的最大利润。

因为整道题只允许一次买入，所以买入只能发生在某一天，且买入后的收益就是-prices[i]；要么今天买入，要么沿用之前某一个更便宜的买入点。写成转移式：

• hold[i] = max(hold[i-1], -prices[i])
• sold[i] = max(sold[i-1], hold[i-1] + prices[i])

第一个式子其实就是在取“历史最低价的相反数”，第二个式子就是在算“今天卖出能拿到的利润”。状态机跑完之后答案就是sold[n-1]。

用代码写出来就是：

def max_profit_dp(prices): hold = float('-inf') sold = 0 for price in prices: sold = max(sold, hold + price) hold = max(hold, -price) return sold

这个版本和前面的单变量扫描本质上是同一个算法，但状态机写法有一个巨大的好处：后面遇到冷冻期、手续费这些变体时，只需要在状态转移里加条件或加状态，不需要重新发明思路。这也是为什么我建议把这两种写法都理解一遍。

3. 边界条件与实现细节：这些坑我替你们踩过了

3.1 空数组和单元素数组

如果数组长度小于 2，根本不存在“买一天卖一天”的可能，直接返回 0。很多新手在写min_price = prices[0]初始化时会忘掉空数组的情况，导致越界访问。稳妥的做法有两种：要么先判空，要么用float('inf')作为初始值。

def max_profit(prices): if not prices: return 0 min_price = prices[0] best = 0 for price in prices[1:]: best = max(best, price - min_price) min_price = min(min_price, price) return best

3.2 单调下跌时答案必须是 0

[7,6,4,3,1]这种例子考察的是“不交易”的语义。如果你把best初始化为负数，或者直接返回max(best, 0)之前没有处理负值，结果就会出错。一个很简单的心法：只要你不强制交易，最差情况就是不赚不亏，所以答案永远不会小于 0。初始化best = 0本身就是对这个语义的保证。

3.3 “买入日必须早于卖出日”的时间语义

暴力解里我写的是j从i + 1开始，就是为了确保卖出日在买入日之后。有些人会用for j in range(n)然后加if j != i的条件，虽然也能跑，但语义不清晰，而且会把同一天买卖的情况也纳入计算。同一天买卖利润是 0，不影响最终答案，但这种写法容易在变体题里埋雷，比如冷冻期版本里同一天买卖会绕过冷冻限制，导致逻辑错误。养成j = i + 1的书写习惯更安全。

3.4 变量初始化与溢出问题

min_price = float('inf')这种写法在 Python 里非常方便，但在 C++ 或 Java 里对应的是INT_MAX，然后用min函数更新。注意如果价格数组允许出现极大值（比如到 10^9 量级），利润prices[j] - prices[i]可能超过 32 位整数的表示范围，这时候要用long long或 64 位整数。很多竞赛场景不会在这种基础题上卡溢出，但养成“先看数据范围再定变量类型”的习惯，对后面做难题很有帮助。

4. 同源头变体题：从“只做一笔”到“随便做几笔”

4.1 无限次交易版：把每个上升段都吃掉

第一个变体是允许无限次交易，但前提是卖完才能再买，且同一时刻只能持有一股。这时有个很漂亮的贪心结论：只要今天的价格比昨天高，就认为昨天买入、今天卖出能赚差价，把所有正差价加起来就是最大利润。

def max_profit_multi(prices): profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i - 1]: profit += prices[i] - prices[i - 1] return profit

为什么这样是对的？比如[1, 3, 2, 4]，两段上升分别是 1→3 和 2→4，累加得到2 + 2 = 4，等价于第一天买、第二天卖、第三天买、第四天卖。而如果第一段下跌 3→2 时强行持有，反而会吃掉利润。把这个逻辑想明白后，你会发现它和“差分数组取正数求和”是一回事。这个变体不建议用状态机 DP 去做，虽然能做但绕远路，贪心是最直接的。

4.2 冷冻期版：三状态状态机 DP

第二个常见变体是：卖出股票后，第二天不能买入，必须冷冻一天。这个限制一加，之前的两个状态就不够用了。因为“今天能不能买”取决于“昨天是不是刚卖出”，我们需要第三个状态来表达“处于冷冻期”或“刚卖完”的状态。

三个状态定义如下：

• hold：今天结束时手里持有股票；
• rest：今天结束时处于冷冻期（即今天刚卖出）；
• free：今天结束时没有股票，且不在冷冻期，明天可以买入。

转移关系：

• hold可以保持不动，也可以从free状态买入：hold_new = max(hold, free - prices[i])
• rest只能由hold卖出而来：rest_new = hold + prices[i]
• free可以由rest冷却而来，也可以由free继续保持：free_new = max(free, rest)

代码实现：

def max_profit_cooldown(prices): hold = float('-inf') rest = 0 free = 0 for price in prices: new_hold = max(hold, free - price) new_rest = hold + price new_free = max(free, rest) hold, rest, free = new_hold, new_rest, new_free return max(rest, free)

很多人在这个变体上翻车，是因为只用了两个状态，把冷冻期当成“暂停一天”处理，结果状态转移写不对。记住一个原则：状态机里，一个状态对应一种“昨天结束时的局面”，而不是“今天的动作”。想清楚昨天是什么状态、今天做什么动作、今天结束时进入什么状态，转移方程就不会错。

4.3 手续费版：在状态转移里扣钱

第三个变体是每次交易（买入加卖出算一笔，或者单次卖出）要扣固定手续费。由于手续费只影响收益，最简单的方式是在卖出时扣掉，或者买入时扣掉，二选一即可，不要两头都扣。

def max_profit_fee(prices, fee): hold = float('-inf') sold = 0 for price in prices: new_sold = max(sold, hold + price - fee) new_hold = max(hold, sold - price) hold, sold = new_hold, new_sold return sold

这里有个小细节：买入手时扣和卖出时扣的结果完全一样，只是hold的初始化不同。如果你选择买入时扣，那么hold的初始值应该是-prices[0] - fee；选择卖出时扣，就像上面的代码一样在卖出时减掉fee。做题时选一种写清楚注释即可。这个变体和无限次交易版对比很有意思：没有手续费时贪心最优，有手续费后贪心可能会因为频繁小额交易被手续费吃掉利润，反而要用 DP 来权衡“要不要做这笔”。

4.4 最多 k 次交易版：二维 DP 与优化

最后一个重量级变体是限制最多交易 k 次。这时贪心彻底失效，冷冻期状态机也不够用，需要一个二维状态：dp[k][i]表示“最多进行 k 次交易，在第 i 天结束时”的最大利润。转移式是：

dp[k][i] = max(dp[k][i-1], prices[i] - prices[j] + dp[k-1][j-1])

其中第二项表示在第 j 天买入、第 i 天卖出，加上之前最多 k-1 次交易的利润。直接枚举 j 是 O(kn²)，但可以维护一个变量best_prev = max(dp[k-1][j-1] - prices[j])在遍历过程中实时更新，把复杂度压到 O(kn)。这个变体本身可以单独写一篇长文，这里先给出思路框架，把前面几个变体吃透后再来啃它会更顺手。

4.5 变体对照表

从这张表能看出一个规律：限制越复杂，状态越多，但空间几乎都可以优化成常数。这就是状态机 DP 的威力，也是这道题值得反复咀嚼的原因。

5. 面试与实战中的经验：别只背模板，要能讲清“为什么”

5.1 我刷这题时踩过的三个典型坑

第一个坑是直接用全局最大最小相减。前面已经说过，[5, 1, 4]这种例子一测就露馅。后来我把“时间顺序”四个字写在了笔记本首页，做任何数组题都先问自己：这个顺序约束能不能被打破？

第二个坑是在冷冻期版本里少写状态。我一开始天真地认为“休息一天”只需要在买入前判断昨天是否卖出，于是只维护了两个状态，结果在[1, 2, 3, 0, 2]这种例子上答案始终不对。后来把三状态的转移图画在纸上，才意识到冷冻期会影响“买入资格”，而这个资格本身就是一个独立状态。

第三个坑是手续费版本里费用重复扣除。我试过买入时扣一次、卖出时又扣一次，导致利润偏低，调了半天才发现是自己把费用算了两次。这种低级错误在面试紧张时特别容易犯，所以我现在写状态转移时一定会先写注释标明“费用在哪个动作发生时扣除”。

5.2 拿到变体题后的判断顺序

经过这一轮系统练习，我总结出一个相对固定的判断流程：

1. 先确认交易次数限制：1 次、无限次、还是固定 k 次。
2. 再确认有没有附加条件：冷冻期、手续费，或者两者都有。
3. 然后选解法：1 次用单变量扫描；无限次且无手续费用贪心；有附加条件用状态机 DP；k 次用二维 DP。
4. 写代码前先在纸上把状态转移式列出来，特别是状态机的“状态定义”要写清楚，再动手。

这个流程几乎可以套用所有买卖股票类变体题。我在模拟面试中试过，只要第一步和第二步判断对了，后面基本就是机械操作。

5.3 讲给面试官的“答题路径”

如果面试官让你现场做这道题，我个人推荐这样讲：先给暴力解，明确说 O(n²)；然后指出重复计算在哪里，引出“历史最低价”这个核心优化；紧接着补充一句“这个问题也可以用状态机 DP 来建模，两个状态分别是持有和未持有”，把转移式写出来。这样既展示了你对暴力到最优的推导能力，又展示了你对更通用 DP 框架的掌握，比直接甩最优解给面试官要好得多。

如果面试官继续追问变体，不要慌，按上面的判断顺序走，先加状态再改转移。状态机最怕的是“状态定义不清”，所以开头那一句话特别重要：“我用三个状态分别表示持有、冷冻期、可买入”。这句话一说出来，面试官基本就知道你懂这题了。

我自己后来在给别人做模拟面试时，发现一个很灵验的判据：能自己推导出“维护历史最低价”这个思路的候选人，比直接背诵最优解的人，在变体题上的表现要好一大截。因为前者理解的是“为什么要这样优化”，后者记住的只是“答案长这样”。所以这篇内容的最后，我还是想建议你：别急着看最优解，先自己把暴力解写出来，然后盯着双重循环问自己一句——“这两层循环里，哪些计算是重复的？”想明白这个问题，你就不只是会做这一道题，而是掌握了一种通用的优化思维。