文章目录121.买卖股票的最佳时机题目思路举例代码实现Go122.买卖股票的最佳时机II题目思路举例代码实现Go进阶思路动态规划代码实现Go空间优化滚动数组O (1) 空间代码实现Go121.买卖股票的最佳时机题目给定一个数组 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^50 prices[i] 10^4思路想要一次交易的利润最大本质就是在「遍历到当前天为止的最低点」买入在该最低点之后的任意一天卖出取卖出的最大利润遍历过程中只需维护两个关键变量不用额外空间边遍历边更新每个价格只看一次minPrice遍历到当前天时之前所有天的股票最低价格也就是到目前为止最划算的买入价maxProfit遍历到当前天时能获取的最大利润初始为0无利润时直接返回这个值。遍历的核心两步对每个价格都执行先更新最小买入价如果当前价格比minPrice更低就把minPrice换成当前价格找到更划算的买入点再计算当前利润更新最大利润用当前价格 -minPrice得到「当天卖出的利润」如果这个利润比maxProfit大就更新maxProfit关键如果当前价格等于minPrice第一步不会更新等于不是更低第二步计算的利润为0不会超过maxProfit初始0后续只增不减所以无需单独处理等于的情况自然跳过即可。举例初始化minPrice 数组第一个元素题目保证数组非空无越界风险maxProfit 0无利润时直接返回利润为负也取0。场景1正常上涨有盈利输入价格数组[7,1,5,3,6,4]共6天步骤初始化minPrice7maxProfit0第2天价格11 7 →minPrice1利润1-10 → 不大于0maxProfit0第3天价格55 不小于1 →minPrice不变利润5-14 → 大于0 →maxProfit4第4天价格33 不小于1 →minPrice不变利润3-12 → 小于4maxProfit不变第5天价格66 不小于1 →minPrice不变利润6-15 → 大于4 →maxProfit5第6天价格44 不小于1 →minPrice不变利润4-13 → 小于5maxProfit不变。结果maxProfit5即第2天买入、第5天卖出利润最大。场景2持续下跌无盈利输入价格数组[7,6,4,3,1]共5天步骤初始化minPrice7maxProfit0第2天价格66 7 →minPrice6利润6-60 → 不大于0maxProfit0第3天价格44 6 →minPrice4利润4-40 → 不大于0maxProfit0第4天价格33 4 →minPrice3利润3-30 → 不大于0maxProfit0第5天价格11 3 →minPrice1利润1-10 → 不大于0maxProfit0。结果maxProfit0全程股价下跌无盈利可能直接返回0。场景3含等于价格输入价格数组[7,1,1,5,3,6]共6天第2、3天价格均为1含等于步骤初始化minPrice7maxProfit0第2天价格11 7 →minPrice1利润1-10 → 不大于0maxProfit0第3天价格11 不小于1 →minPrice不变利润1-10 → 不大于0maxProfit不变第4天价格55 不小于1 →minPrice不变利润5-14 → 大于0 →maxProfit4第5天价格33 不小于1 →minPrice不变利润3-12 → 小于4maxProfit不变第6天价格66 不小于1 →minPrice不变利润6-15 → 大于4 →maxProfit5。结果maxProfit5和去掉等于价格的数组[7,1,5,3,6]结果一致等于价格无任何影响只需要比较小于即可。代码实现GopackagemainimportfmtfuncmaxProfit(prices[]int)int{minPrice:prices[0]// 初始化为首个元素maxProfit:0// 无利润返回0利润为负也保持0// 从第二个元素开始遍历索引1首个元素已作为初始minPricefori:1;ilen(prices);i{curPrice:prices[i]// 第一步更新到目前为止的最小买入价仅当前价格更小时更新ifcurPriceminPrice{minPricecurPrice}// 第二步计算当天卖出的利润更新最大利润curProfit:curPrice-minPriceifcurProfitmaxProfit{maxProfitcurProfit}}returnmaxProfit}funcmain(){// 直接构造题目给的输入数组 [7,1,5,3,6,4]prices:[]int{7,1,5,3,6,4}res:maxProfit(prices)fmt.Println(res)}// 或funcmain(){varnintfmt.Scan(n)// 读取价格数组的长度prices:make([]int,n)fori:0;in;i{fmt.Scan(prices[i])// 循环读取n个价格到数组}// 计算并打印最大利润res:maxProfit(prices)fmt.Println(res)}// 或funcmain(){varprices[]intvarnumint// 循环不断读取int只要成功读到1个整数就继续读到非数字/输入结束则退出循环forfmt.Scan(num)1{pricesappend(prices,num)}res:maxProfit(prices)fmt.Println(res)}/* 测试用例1 【输入】7 1 5 3 6 4 【预期输出】5 解释买入价格1卖出价格6最大利润 5时间复杂度O (n)仅遍历一次价格数组空间复杂度O (1)仅使用常数个变量packagemainimportfmt// maxProfit 返回最大利润[买入价,卖出价]funcmaxProfit(prices[]int)(int,[2]int){n:len(prices)ifn2{return0,[2]int{0,0}}minPrice:prices[0]// 历史最低价格buyPrice:0sellPrice:0maxProfitVal:0fori:1;in;i{// 更新历史最低点可以在这里买ifprices[i]minPrice{minPriceprices[i]}else{// 在今天卖出算利润profit:prices[i]-minPriceifprofitmaxProfitVal{maxProfitValprofit buyPriceminPrice sellPriceprices[i]}}}ifmaxProfitVal0{return0,[2]int{0,0}}returnmaxProfitVal,[2]int{buyPrice,sellPrice}}funcmain(){prices:[]int{7,2,5,9,1,3,6,4}profit,pair:maxProfit(prices)fmt.Printf(%d, %v\n,profit,pair)// 输出7, [2 9] 和样例完全一致}读取单个数字 / 字符串fmt.Scan(变量名)varnint// 定义一个整数变量nfmt.Scan(n)// 终端输入一个数字比如6n就等于6varsstringfmt.Scan(s)// 终端输入一个字符串s就等于该字符串循环读取多个值for循环 fmt.Scan(数组元素)// 步骤1定义变量接收数组长度读取长度n 【必须加】varnintfmt.Scan(n)// 步骤2初始化一个长度为n的切片/数组 【固定写法】nums:make([]int,n)// 切片算法面试首选比数组灵活// 步骤3循环n次读取n个数字存入切片 【必须加nums[i]】fori:0;in;i{fmt.Scan(nums[i])// 每次读取一个数字赋值给nums[i]}读取两个数字vara,bintfmt.Scan(a,b)// 终端输入3 5a3b5fmt.Println(ab)// 输出8122.买卖股票的最佳时机II题目给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。在每一天你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而你可以在同一天多次买卖该股票但要确保你持有的股票不超过一股。返回你能获得的最大利润 。示例 1输入prices [7,1,5,3,6,4]输出7解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3。最大总利润为 4 3 7 。示例 2输入prices [1,2,3,4,5]输出4解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。最大总利润为 4 。示例 3输入prices [7,6,4,3,1]输出0解释在这种情况下, 交易无法获得正利润所以不参与交易可以获得最大利润最大利润为 0。提示1 prices.length 3 * 10^40 prices[i] 10^4思路只要后一天股价 前一天股价就在前一天买入、后一天卖出赚取该段差价股价下跌/持平则不操作。最终所有上涨差价的总和就是最大利润。为什么“只赚相邻上涨差价”是最优的1数学等价性拆分交易 长期持有对于任意持续上涨区间prices[i] prices[i1] ... prices[j]拆分交易利润(prices[i1]-prices[i]) (prices[i2]-prices[i1]) ... (prices[j]-prices[j-1])单次长期交易利润prices[j] - prices[i]两者展开后中间项完全抵消最终结果相等比如1→2→3→4→5拆分赚11114长期持有赚5-14。这意味着“每天买卖赚小差价”只是数学上的等价拆解并非真的要高频操作实际可简化为“低点买、高点卖”利润完全一致。2覆盖所有盈利可能无遗漏相邻天数的判断能精准捕捉所有独立上涨区间比如7,1,5,3,6,4中的1→5、3→6不会放过任何可盈利的差价而“跳天判断”要么不可行中间下跌时持有会亏损要么利润与相邻判断相等无任何优势。举个反例如果股价是[1,3,2,4]有人觉得 “1 买 4 卖”利润 3比 “1 买 3 卖、2 买 4 卖”利润 224更优→ 错“1 买 4 卖” 的实际操作中3→2 下跌时持有股票相当于 “赚了 1→3 的 2亏了 3→2 的 1赚了 2→4 的 2”总利润 2-123反而比相邻贪心的 4 少 —— 这就是 “跳天操作” 的问题中间下跌会吃掉部分利润而相邻贪心会在下跌前卖出避免亏损。具体步骤初始化定义maxProfit 0用于累加总利润遍历数组从第2天索引1开始逐个对比当天与前一天的股价若prices[i] prices[i-1]将prices[i] - prices[i-1]加到maxProfit若prices[i] ≤ prices[i-1]不操作利润保持不变返回结果遍历结束后maxProfit即为最大利润全程下跌时利润为0符合题目要求。举例示例1prices [7,1,5,3,6,4]1→5差价4 →maxProfit43→6差价3 →maxProfit7其余天数下跌/持平无操作最终利润7与示例一致。示例2prices [1,2,3,4,5]每天差价1累加得4 → 与“1买5卖”利润一致。示例3prices [7,6,4,3,1]所有天数股价下跌利润保持0。代码实现GopackagemainimportfmtfuncmaxProfit(prices[]int)int{maxProfit:0// 从第2天索引1开始遍历对比当天与前一天的股价// 索引0是第1天无前置价格无需处理fori:1;ilen(prices);i{ifprices[i]prices[i-1]{// 若当天价格 前一天价格赚取该段差价maxProfitprices[i]-prices[i-1]}// 价格下跌/持平时不操作利润保持不变无需额外处理}returnmaxProfit}funcmain(){varnintfmt.Scan(n)prices:make([]int,n)fori:0;in;i{fmt.Scan(prices[i])}res:maxProfit(prices)fmt.Println(res)}时间复杂度O (n)仅遍历一次价格数组空间复杂度O (1)仅使用 maxProfit 一个变量进阶思路动态规划1. 状态定义dp[i][0]第i天不持有股票的最大利润dp[i][1]第i天持有股票的最大利润。2. 状态转移不持有股票要么前一天也不持有要么前一天持有、今天卖出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])。dp[i][0]卖出操作会让利润增加prices[i]取「不操作」和「卖出」中利润更大的情况dp[i][1]买入操作会让利润减少-prices[i]取「不操作」和「买入」中利润更大的情况3. 初始状态dp[0][0] 0第0天不持有利润0dp[0][1] -prices[0]第0天买入利润为负。4. 最终结果dp[n-1][0]最后一天不持有股票的利润必然高于持有。代码实现GopackagemainimportfmtfuncmaxProfit(prices[]int)int{n:len(prices)// 边界处理如果价格数组为空直接返回0ifn0{return0}// 定义dp数组dp[i][0]表示第i天不持有股票的最大利润dp[i][1]表示持有dp:make([][2]int,n)// 初始状态第0天第一天的状态dp[0][0]0// 第0天不持有股票利润为0dp[0][1]-prices[0]// 第0天买入股票利润为 -股价成本// 遍历从第1天开始索引1逐天更新状态fori:1;in;i{// 状态转移1第i天不持有股票的两种情况// 情况1前一天也不持有利润不变情况2前一天持有今天卖出利润前一天持有利润今天股价dp[i][0]max(dp[i-1][0],dp[i-1][1]prices[i])// 状态转移2第i天持有股票的两种情况// 情况1前一天也持有利润不变情况2前一天不持有今天买入利润前一天不持有利润-今天股价dp[i][1]max(dp[i-1][1],dp[i-1][0]-prices[i])}// 最终结果最后一天不持有股票的利润持有股票的话未卖出利润必然更低returndp[n-1][0]}funcmax(a,bint)int{ifab{returna}returnb}funcmain(){varnintfmt.Scan(n)prices:make([]int,n)fori:0;in;i{fmt.Scan(prices[i])}res:maxProfit(prices)fmt.Println(res)}时间复杂度O (n)仅遍历一次价格数组空间复杂度O (n)创建了长度为 n、每个元素为长度 2 的数组 dp空间优化滚动数组O (1) 空间上述代码用了 O (n) 空间实际可优化为 O (1)因为每天的状态仅依赖前一天适合大数据量场景代码实现GopackagemainimportfmtfuncmaxProfit(prices[]int)int{n:len(prices)// 边界处理如果价格数组为空直接返回0ifn0{return0}// 用两个变量代替dp数组滚动更新hold:-prices[0]// 持有股票的最大利润初始为第0天买入notHold:0// 不持有股票的最大利润初始为第0天不操作fori:1;in;i{// 先保存更新前的状态避免覆盖preHold:hold preNotHold:notHold// 更新不持有状态前一天不持有 或 前一天持有今天卖出notHoldmax(preNotHold,preHoldprices[i])// 更新持有状态前一天持有 或 前一天不持有今天买入holdmax(preHold,preNotHold-prices[i])}returnnotHold}funcmain(){varnintfmt.Scan(n)prices:make([]int,n)fori:0;in;i{fmt.Scan(prices[i])}res:maxProfit(prices)fmt.Println(res)}时间复杂度O (n)仅遍历一次价格数组空间复杂度O (1)