一道股票题，为什么面试官能问出五六种变体？

一道股票题为什么面试官能问出五六种变体1. 为什么写这篇之前博客写的排序算法、顺序表都是实现一个具体结构——给你一个明确的定义你把它用代码写出来。这篇文章要聊的是另一种能力拿到一个开放式问题你的解法如何一步步进化。LeetCode 上有一套经典的买卖股票系列题从只能交易一次121到可以交易无数次122再到限制交易次数123/188、含冷冻期309、含手续费714。面试官特别喜欢这套题因为他只需要改一个条件就能考察你不同层次的算法能力。本文以 121 和 122 为核心记录三种思维方式的演变暴力 → 贪心 → DP 状态机。重点是为什么这样想而不是怎么写代码。2. 题目速览121. 买卖股票的最佳时机只能买卖一次题目描述给定数组pricesprices[i]是第i天的股价。只能选择某一天买入在未来的某一天卖出。求最大利润。如果无法获利返回 0。示例输入[7, 1, 5, 3, 6, 4]输出5解释第2天买入1第5天卖出6利润6-15122. 买卖股票的最佳时机 II可以买卖无数次题目描述规则同上但不限制交易次数。手里最多只能持有一股同一天可以先卖后买。示例输入[7, 1, 5, 3, 6, 4]输出7解释1买5卖赚43买6卖赚3总利润73. 第一种思维暴力法——最直观的想法拿到一道题最朴素的想法就是枚举所有可能。核心思路对于 121只能交易一次所有可能的买点是i所有可能的卖点是j i。遍历每一对(i, j)算差价取最大值。intmaxProfit(int*prices,intpricesSize){intmax0;for(inti0;ipricesSize-1;i){for(intji1;jpricesSize;j){intprofitprices[j]-prices[i];if(profitmax)maxprofit;}}returnmax;}为什么它是对的因为它穷举了所有可能的买卖组合。只要存在一种赚钱的方式它一定能找到。为什么它不能用时间复杂度O(n2)O(n^2)O(n2)。LeetCode 的测试数据动辄上万O(n2)O(n^2)O(n2)直接超时。暴力法是正确的但它是不可用的。暴力的价值暴力法不是用来提交的是用来验证你对题目的理解是否正确。如果你连暴力都写不出来说明你还没理解题目在问什么。这是所有算法思考的起点。4. 第二种思维贪心——抓住每一次上涨暴力法的瓶颈在于枚举了所有可能包括很多显然不可能的组合。能不能跳过那些没用的计算核心思路针对 122 无限次交易既然交易次数不限而且同一天可以先卖后买那么连续上涨的大利润可以拆成每天的小利润。比如[1, 2, 3]利润3 - 1 2等价于(2-1) (3-2) 2。于是策略变得极其简单只要今天比昨天贵就在昨天买入、今天卖出赚走这个差价。如果今天比昨天便宜就不操作。intmaxProfit(int*prices,intpricesSize){if(pricesSize2)return0;intprofit0;for(inti1;ipricesSize;i){if(prices[i]prices[i-1]){profitprices[i]-prices[i-1];}}returnprofit;}手动推演[7, 1, 5, 3, 6, 4]天数昨天价格今天价格操作累计利润171跌不动0215涨赚44353跌不动4436涨赚37564跌不动7贪心的局限贪心能完美解决 122无限次但有两个问题对 121 无效只能交易一次时不能把大利润拆成小利润累加。对变体无效如果加上手续费714或冷冻期309贪心的只看当天差价策略就失效了。总结贪心是战术——在特定条件下极快极简但它不是战略——条件一变它可能完全失效。5. 第三种思维DP 状态机——通用框架贪心失效时怎么办我们需要一种能应对规则变化的通用框架。这就是 DP 状态机。核心思路不看操作看状态我们不关心哪天买、哪天卖只关心每天结束时手里是什么状态口袋里有多少钱。定义两个变量cash当天结束时手里没有股票最多赚了多少钱空仓hold当天结束时手里持有股票最多赚了多少钱持仓每天的状态只依赖前一天的状态。状态转移针对 122 无限次交易今天空仓**cash**怎么来要么昨天就空仓今天啥也没干 →cash保持不变要么昨天持仓今天卖了 →hold prices[i]变现cash max(cash, hold prices[i])今天持仓**hold**怎么来要么昨天就持仓今天啥也没干 →hold保持不变要么昨天空仓今天买入 →cash - prices[i]用累计利润买hold max(hold, cash - prices[i])代码实现推荐用临时变量虽然本题允许同一天先卖后买顺序更新也行但为了保证逻辑严密、以后扩展到限制交易次数时不出 bug建议用临时变量保存前一天的状态intmaxProfit(int*prices,intpricesSize){if(pricesSize2)return0;intcash0;// 第0天空仓利润为0inthold-prices[0];// 第0天买入利润为负for(inti1;ipricesSize;i){intprev_cashcash;// 保存前一天的状态intprev_holdhold;// 今天空仓 max(昨天空仓, 昨天持仓 今天卖出)cashprev_cashprev_holdprices[i]?prev_cash:prev_holdprices[i];// 今天持仓 max(昨天持仓, 昨天空仓 - 今天买入)holdprev_holdprev_cash-prices[i]?prev_hold:prev_cash-prices[i];}returncash;}手动推演[7, 1, 5, 3, 6, 4]天数价格prev(cash, hold)cash max(…)hold max(…)最终(cash, hold)07———(0, -7)11(0, -7)max(0, -71) 0max(-7, 0-1) -1(0, -1)25(0, -1)max(0, -15) 4max(-1, 0-5) -1(4, -1)33(4, -1)max(4, -13) 4max(-1, 4-3) 1(4, 1)46(4, 1)max(4, 16) 7max(1, 4-6) 1(7, 1)54(7, 1)max(7, 14) 7max(1, 7-4) 3(7, 3)返回cash 7。6. 三解法对比维度暴力法贪心DP 状态机时间复杂度O(n2)O(n^2)O(n2)O(n)O(n)O(n)O(n)O(n)O(n)空间复杂度O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)可扩展性仅限无限次交易适配所有股票变体代码复杂度简单极简中等适用场景仅验证思路122 最优解面试展现通用能力7. 为什么面试官能问出五六种变体因为 DP 状态机这套框架改一行公式就能适配一个新题目题目核心变化关键改动121一次买入时只能用初始本金不能用历史利润hold max(hold, -prices[i])122无限次买入时可以用累计利润hold max(hold, cash - prices[i])714含手续费卖出时扣手续费cash max(cash, hold prices[i] - fee)309冷冻期卖出后隔一天才能买引入prev_prev_cash买入时用两天前的状态123最多两笔限制交易次数 k2将cash和hold扩展为二维数组dp[k1][2]188最多 k 笔限制交易次数为任意 k同 123k 作为参数传入面试官只需要改一个条件——加手续费、加冷冻期、限制次数——就能考察你是在背答案还是真正理解了底层框架。8. 学习体会这道题给我最大的收获不是会做股票题了而是看到了解法是如何一步步进化的暴力是起点用最简单粗暴的方式验证自己对题意的理解贪心是优化抓住题目的特殊条件无限次交易把O(n2)O(n^2)O(n2)砍到O(n)O(n)O(n)DP 是升维跳出具体条件的限制构建一个能应对规则变化的通用框架以后再遇到新题我会先问自己三个问题最笨的方法是什么先保证做对有没有贪心的可能利用特殊条件加速如果规则会变DP 怎么写为扩展留后路解法不是孤立的它们是一条进化链。每一步都在解决上一步的局限性。