3招搞定区间交易法，搞定这道高频面试题 别再被官方文档里那些晦涩的数学公式劝退了。刚翻完 LeetCode 题解，脑子还是一团浆糊？ 别慌，这不是你笨，是资料没讲人话。 今天咱们不整虚的，直接拆解区间交易法。这是算法面试里的高频面试题，也是很多转行开发者卡住脖子的硬骨头。 概念速懂：它到底在算啥？ 很多人一听到“区间交易”，脑子里就蹦出股票 K 线图。其实，在算法语境下，它解决的是一个很具体的问题： 给定一个价格数组，在不持有股票的情况下，求最大利润。 注意两个核心约束：可以多次买卖：今天买明天卖，明天买后天卖，想交易几次都行。 必须空仓：你手里只能有一支股票，不能同时持有两支。听起来像废话？不，这正是难点所在。 传统思维是“找局部最低点买入，找局部最高点卖出”。但现实情况往往更复杂：价格可能是锯齿状的，可能是单边上涨，也可能是先跌后涨再跌。 如果只用“贪心算法”（即只要明天比今天高，就今天买明天卖），虽然能得到正确答案，但在面试中，面试官往往想考察你对状态机或动态规划的理解，而不仅仅是贪心。 区间交易法的本质，是将交易过程分解为若干个独立的“区间”，在每个区间内寻找最优解。 举个游戏开发的例子： 想象你在做一款经营类游戏，玩家每天可以买卖一种资源。如果资源价格趋势是 1, 2, 3, 4，玩家应该第一天买，最后一天卖。 如果趋势是 1, 4, 2, 5，玩家应该第一天买第二天卖，第三天买第四天卖。区间交易法就是帮你自动识别这些“最佳买卖窗口”。 为什么这值得深究？因为这种思维模型不仅适用于股票，还适用于任何资源调度、任务分配、甚至游戏里的背包优化场景。 环境准备：工欲善其事 在动手写代码之前，先确保你的开发环境是干净的。 对于 Python 开发者，你只需要标准的 Python 3.8+ 环境。不需要安装任何第三方库，因为这道题考察的是纯算法逻辑。 # 验证环境是否就绪 import sys print(fPython Version: {sys.version}) # 输出示例: Python Version: 3.10.0 (default, Oct 1 2021, 15:38:32) [GCC 9.3.0] on linux对于前端或后端开发者，如果你习惯用 JavaScript 或 TypeScript，逻辑是一样的。这里我们以 Python 为主，因为它最接近伪代码，便于理解算法核心。 关键工具建议：调试器：不要用 print 调试，用 pdb 或 IDE 自带的断点调试。你需要逐行观察 cash（现金）和 hold（持有股票）状态的变化。 画纸：真的，拿张纸画一下状态转换图。在开始编码前，问自己两个问题：我在第 i 天结束时，手里有没有股票？ 如果有，我的现金是多少？如果没有，我的现金是多少？这两个问题，构成了我们算法的状态定义。 核心语法：状态机拆解 这是全文最硬核的部分。请拿出笔，跟着我的思路走。 我们定义两个状态变量：sell：表示当前不持有股票时的最大现金余额。 buy：表示当前持有股票时的最大现金余额（注意：这里买股票是负现金，所以 buy 初始值应该是 -infinity，表示还没买，或者说买了就是亏到极点）。状态转移方程：更新 sell（卖出状态）： 到了第 i 天，如果不持有股票，有两种可能：昨天就不持有股票，今天也没操作：sell = sell 昨天持有股票，今天卖掉了：sell = buy + prices[i]我们要取最大值： sell = max(sell, buy + prices[i])更新 buy（买入状态）： 到了第 i 天，如果持有股票，有两种可能：昨天就持有股票，今天没操作：buy = buy 昨天不持有股票，今天买入了：buy = sell - prices[i]我们要取最大值（因为 buy 是负数，我们要让它尽可能“不那么负”，即损失最小）： buy = max(buy, sell - prices[i])初始状态：sell = 0：第一天开始前，我没股票，现金为 0。 buy = -prices[0]：第一天开始前，我假设已经买了第一天的股票，所以现金是负的。为什么这个逻辑成立？ 这其实是动态规划的一种简化形式。sell 和 buy 分别代表了第 i 天结束时，处于“空仓”和“持仓”两种状态下的最优解。 这里有一个常见的误区：很多人认为 buy 和 sell 必须在同一天更新。其实，在代码实现中，顺序很重要。 如果先更新 sell，再更新 buy，会发生什么？ buy 会使用刚刚更新过的 sell 值。这意味着，你在同一天既卖了又买了。这在现实中是允许的（T+0 交易），但在某些严格的算法题中（如 LeetCode 122 题），这种操作是合法的，因为题目允许“在同一天进行多次交易”，或者更准确地说，允许“当天卖出的股票当天买入”。 但如果题目限制“卖出后第二天才能买入”（LeetCode 309 题，含冷冻期），那么状态转移就需要增加一个 freeze 状态，或者调整更新顺序。 对于本篇讨论的基础区间交易法（LeetCode 122 模式），上述逻辑是标准解法。 完整代码示例：从理论到实战 光说不练假把式。下面给出两段可运行的代码，分别对应基础版和空间优化版。 示例 1：标准动态规划解法 这段代码清晰展示了状态转移的过程，适合初学者理解。 def max_profit_basic(prices):基础版：使用两个变量跟踪状态时间复杂度: O(n)空间复杂度: O(1)if not prices or len(prices) 2:return 0# 初始化状态# sell: 当前不持有股票的最大现金# buy: 当前持有股票的最大现金 (实际上是负值，代表成本)sell = 0buy = -prices[0]for i in range(1, len(prices)):price = prices[i]# 关键：先更新 sell，再更新 buy# 因为今天的 sell 状态可能依赖于昨天的 buy 状态# 而今天的 buy 状态可能依赖于昨天的 sell 状态# 1. 更新卖出状态：要么昨天就没卖，要么今天卖了prev_sell = sellsell = max(sell, buy + price)# 2. 更新买入状态：要么昨天就买了，要么今天买了# 注意：这里使用的是更新前的 prev_sell 还是更新后的 sell？# 在 LeetCode 122 中，允许当天卖出后当天买入，所以可以直接用 sell# 但为了严谨，我们思考一下：# 如果今天买，意味着我昨天没股票。昨天的最优卖出状态是 prev_sell。# 所以严格来说，buy = max(buy, prev_sell - price)# 但在 LeetCode 122 的逻辑里，sell 和 buy 的更新顺序隐含了 T+0 的灵活性。# 让我们验证一下：# 如果 prices = [1, 2]# i=1, price=2# sell = max(0, -1 + 2) = 1# buy = max(-1, 1 - 2) = -1 (这里如果用新的 sell=1, 1-2=-1; 如果用旧的 sell=0, 0-2=-2)# 显然 -1 -2，所以用新的 sell 会导致 buy 变大（损失变小）。# 这符合“当天卖完当天买”的逻辑吗？# 是的。如果今天价格高，我卖出后现金多了，我可以立刻用这些现金再买一次（虽然价格一样，但逻辑上允许）。# 不过，对于标准 LeetCode 122，通常直接用 sell 即可，因为题目允许多次交易。buy = max(buy, sell - price)return sell# 测试用例 prices_1 = [7, 1, 5, 3, 6, 4] print(fTest 1: {max_profit_basic(prices_1)}) # 预期输出: 7prices_2 = [1, 2, 3, 4, 5] print(fTest 2: {max_profit_basic(prices_2)}) # 预期输出: 4prices_3 = [2, 4, 1] print(fTest 3: {max_profit_basic(prices_3)}) # 预期输出: 2逐行讲解关键点：buy = -prices[0]：这是很多初学者报错的地方。为什么是负数？因为买股票是支出。 sell = max(sell, buy + price)：这一步确保我们要么保持之前的最高收益，要么在今天这个价位卖出能赚更多。 buy = max(buy, sell - price)：这一步确保我们要么保持之前的最低成本，要么在今天这个价位买入能减少亏损（或增加后续潜力）。示例 2：贪心算法对比（进阶理解） 虽然状态机是通用解法，但对于 LeetCode 122 这种特定题型，贪心算法更为简洁。这也是面试官喜欢问的“你有没有更优解”。 def max_profit_greedy(prices):贪心版：只要明天比今天高，就赚这个差价时间复杂度: O(n)空间复杂度: O(1)if not prices:return 0profit = 0for i in range(1, len(prices)):if prices[i] prices[i - 1]:profit += prices[i] - prices[i - 1]return profit# 验证贪心解法与状态机解法结果一致 prices_test = [7, 1, 5, 3, 6, 4] print(fGreedy Test: {max_profit_greedy(prices_test)}) # 预期输出: 7为什么贪心有效？ 数学上可以证明，任何多次交易的最大利润，等于所有“正差值”之和。 例如 [1, 2, 3]：贪心：(2-1) + (3-2) = 1 + 1 = 2 一次性买卖：3 - 1 = 2 结果一样。但在面试中，先写状态机，再提贪心优化，能体现你的思维深度。 常见报错：这些坑我替你踩过了 在实际开发和面试中，以下三个问题最为常见。 1. 边界条件未处理 错误代码： def max_profit_error(prices):sell = 0buy = -prices[0] # 如果 prices 为空，这里会 IndexError...修复： 永远先检查数组长度。 if not prices or len(prices) 2:return 02. 状态更新顺序错误 在含“冷冻期”或“手续费”的变种题中，如果直接原地更新 sell 和 buy，可能会导致状态污染。 正确做法： 使用临时变量保存旧状态。 prev_sell = sell prev_buy = buy sell = max(prev_sell, prev_buy + price) buy = max(prev_buy, prev_sell - price)虽然对于基础版 LeetCode 122 这不是必须的，但养成这个习惯，能帮你轻松应对变种题。 3. 混淆“最大利润”与“最终现金” 有些题目问的是“最大利润”，有些问的是“完成所有交易后的最大现金”。如果初始现金为 0，最大利润 = 最终现金 - 0 = 最终现金。 但如果题目允许初始借入（即 buy 初始值为 0 而不是 -inf），逻辑就会变化。 务必仔细读题，确认初始状态。小结：从算法到工程思维 区间交易法不仅仅是一道算法题，它是一种状态建模的能力。 在游戏开发中，你可能会遇到：资源循环：玩家采集资源、加工、出售。每个环节都是状态转换。 任务系统：接任务、做任务、交任务。状态机是核心。 背包系统：物品栏满、不满、丢弃、拾取。当你把问题抽象为状态和转移，而不是盯着具体的数字看，你就掌握了算法的精髓。 回到开头的痛点：官方文档太长抓不住重点。 其实，所有复杂的算法，剥开外衣，核心逻辑往往只有几行代码。关键在于理解状态的含义和转移的条件。 对于转岗的开发者，我不建议你死记硬背代码模板。 建议你：手动模拟：拿一支笔，在纸上画出 [1, 2, 3] 的价格变化，追踪 sell 和 buy 的值。 变种练习：尝试修改代码，加入“交易次数限制”或“手续费”，看看状态机如何变化。权威来源提示： 在分布式系统或网络协议设计中，类似的状态机思维被广泛应用。例如 RFC 2616 (HTTP/1.1) 规范中，对请求-响应周期的状态描述，就隐含了类似的“状态流转”逻辑。虽然领域不同，但状态明确化的思想是相通的。 最后，留给你一个思考题： 如果题目要求“最多只能交易两次”，你该如何扩展上面的状态机？ 提示：你需要增加两个状态变量，分别代表“完成第1次交易后”和“完成第2次交易后”的最大利润。 你更常用哪种写法？是倾向于直观的贪心，还是严谨的状态机？评论区交流，看看大家的实战经验。