1. 从“高僧斗法”到“股票买卖”蓝桥杯贪心算法的实战脉络如果你刷过蓝桥杯的真题可能会对“高僧斗法”这道题有印象。它本质上是一个博弈论问题但解题的钥匙往往藏在一种看似简单、实则精妙的思维方式里——贪心。今天我们不聊高僧来聊聊一个更贴近生活、在蓝桥杯国赛中也频频出现的经典模型股票买卖Ⅱ。很多人第一次看到这个题目会下意识地想到动态规划毕竟“买卖股票”是DP的经典例题。但题目后缀那个醒目的“贪心”就像一位经验丰富的出题人在对你眨眼“别想复杂了这次有更巧的路。”我参加过也辅导过不少算法竞赛发现很多同学对贪心算法有种“既爱又恨”的矛盾心理。爱的是它的代码往往简洁得令人发指恨的是你永远不确定自己的“贪心策略”是否真的能“贪”到全局最优。股票买卖Ⅱ这道题就是一个绝佳的例子它能帮你把贪心算法的“感觉”沉淀为清晰的“逻辑”。我们不需要复杂的DP状态数组只需要遍历一次价格序列抓住“趋势”的本质就能用几行代码解决问题。这背后是对问题模型的深刻洞察也是竞赛中追求时间与空间双重效率的体现。接下来我们就彻底拆解这道题看看贪心算法是如何在这个场景下展现出它四两拨千斤的魅力的。2. 问题重述与核心模型抽象无限次交易的利润从何而来题目“股票买卖Ⅱ”通常是这样描述的给定一个长度为n的数组prices其中prices[i]表示第i天的股票价格。你可以完成多笔交易即买卖股票多次但你必须遵守以下规则你不能同时参与多笔交易即在再次购买股票前必须出售掉之前的股票。你可以当天卖出股票并在同一天重新购买这相当于不操作但为我们的思路提供了关键切入点。我们的目标是计算你能获得的最大利润。首先我们要把这个问题从“买卖股票”这个具体场景中抽象出来。抛开股票我们面对的是一个数字序列。所谓的“利润”就是通过一系列“低买高卖”的操作从序列的波动中获取差值总和。规则限制我们手里最多只能持有一支股票这防止了复杂的持仓叠加。而允许无限次交易则是问题的关键它让我们可以把每一次“上涨”都视为获利的机会。这里最核心的思维转换是最大利润并不来自于预测波峰波谷进行“抄底逃顶”而是来自于捕获所有的“上升段”。举个例子假设价格序列是[7, 1, 5, 3, 6, 4]。如果你试图找到最低点1买入最高点6卖出那么利润是5。但如果我们分解来看从1到5利润是4从3到6利润是3。总利润是437大于5。为什么因为你抓住了两段上升趋势。贪心算法的思想就在这里萌芽——我们不需要关心整体的、跨度大的波段只需要关心相邻两天只要后一天比前一天价格高这个差价就是我们可以稳稳获得的利润。注意这个结论成立的前提是交易次数无限且没有手续费。如果交易有成本或者限制交易次数这个贪心策略就不再适用必须使用动态规划。这也是为什么题目明确标注“贪心”它帮你排除了其他复杂情况的干扰让你聚焦于贪心策略本身的有效性证明。所以我们的模型被抽象为遍历价格序列计算所有prices[i] - prices[i-1]的正差值即后项减前项为正并将这些正差值累加起来结果就是最大利润。这个模型干净利落是贪心算法“局部最优导致全局最优”的典型体现。3. 贪心策略的可行性证明为什么局部正差之和等于全局最大利润理解了思路我们还需要从逻辑上说服自己为什么把所有上涨日间的差价加起来就是全局最优解这是贪心类题目最关键的环节不能只靠“感觉”。我们可以从两个角度来证明角度一分解法。考虑任意一段价格上升区间[prices[a], prices[b]](a b 且 prices[a] prices[b])。这段区间产生的总利润prices[b] - prices[a]可以分解为从第a天到第b天所有相邻两天正差值的和(prices[a1]-prices[a]) (prices[a2]-prices[a1]) ... (prices[b]-prices[b-1])根据假设这是一个上升区间所以这些相邻差值中正数会被保留负数即下跌日不会被计入我们的贪心策略。实际上整个区间的总涨幅就等于区间内所有“上升日”涨幅的总和。因此捕获每一个相邻的上升片段等价于捕获了所有可能上升区间的全部利润。任何一笔跨越多个波动的交易其利润都可以被拆解为多笔更小、更即时的交易之和且不会违反“不能同时持有多仓”的规则因为可以在理论上当天完成买卖切换。角度二决策包容性。我们每一天都面临一个决策如果明天价格更高我今天就持有或买入如果明天价格更低我今天就卖出或不买入。贪心策略ans max(0, prices[i] - prices[i-1])完美地模拟了这个决策过程。max(0, ...)意味着我们只对上涨做出反应获取利润。对于下跌我们选择忽略不产生负利润。可以证明任何不采用这种“逢涨必取”策略的方案其利润都不会超过这个策略。因为如果你在某段上涨(i-1, i)中选择了不获利那么你要么错过了这部分利润要么需要依赖后面更高的价格来弥补但这又可能受制于持仓规则反而可能错过其他机会。因此贪心地获取每一个可见的利润是最安全且最优的选择。这个证明过程虽然不涉及复杂的数学公式但它建立了我们对算法正确性的坚实信心。在竞赛中即使时间紧迫在头脑中快速过一遍这个逻辑也能让你写代码时更有底气。4. 代码实现与逐行解析从思路到AC的精确转换理论清晰之后实现就变得异常简单。这里给出 Python、Java 和 C 三种常见竞赛语言的实现并附上详细注释。Python 实现def maxProfit(prices): 计算无限次交易下的最大利润。 :type prices: List[int] :rtype: int if not prices or len(prices) 2: return 0 max_profit 0 for i in range(1, len(prices)): # 核心贪心逻辑如果今天价格比昨天高就把这部分差价作为利润 diff prices[i] - prices[i-1] if diff 0: max_profit diff return max_profit # 测试用例 if __name__ __main__: print(maxProfit([7,1,5,3,6,4])) # 输出7 print(maxProfit([1,2,3,4,5])) # 输出4 print(maxProfit([7,6,4,3,1])) # 输出0第1-4行函数定义和边界条件检查。如果价格列表为空或只有一天无法交易利润为0。第7-11行核心循环。从第2天索引1开始遍历。diff prices[i] - prices[i-1]计算相邻两天的差价。if diff 0:是贪心决策点只收集正利润。max_profit diff累加利润。时间复杂度 O(n)只需一次遍历。空间复杂度 O(1)只使用了常数个额外变量。Java 实现public class Solution { public int maxProfit(int[] prices) { if (prices null || prices.length 2) { return 0; } int maxProfit 0; for (int i 1; i prices.length; i) { int diff prices[i] - prices[i-1]; if (diff 0) { maxProfit diff; } } return maxProfit; } }Java版本逻辑完全一致注意数组的边界判断和循环写法。C 实现#include vector using namespace std; class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); if (n 2) return 0; int profit 0; for (int i 1; i n; i) { int diff prices[i] - prices[i-1]; if (diff 0) profit diff; } return profit; } };C版本同样简洁使用vector容器注意循环变量从i1开始。这三段代码都清晰地体现了贪心的核心不预测、不等待见到上涨就视为利润落袋。代码本身几乎没有陷阱但正是这种简洁常常让初学者怀疑其正确性。所以我们更需要理解前面部分的策略证明。5. 与动态规划解法的对比分析理解贪心的适用边界为了更深刻地理解贪心算法的妙处我们有必要看看这个问题的动态规划解法。这能帮助我们明确在什么条件下贪心是更优解以及当条件变化时我们该如何切换思路。动态规划通常需要定义状态。对于股票买卖问题一个经典的状态定义是dp[i][0]表示第i天结束时不持有股票的最大利润。dp[i][1]表示第i天结束时持有股票的最大利润。状态转移方程为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[0][0] 0,dp[0][1] -prices[0]。 最终答案是dp[n-1][0]即最后一天不持有股票的最大利润。用DP解[7,1,5,3,6,4]过程如下表天数 (i)价格dp[i][0] (不持有)dp[i][1] (持有)说明070-7初始化不持有利润0持有则花费7买入11max(0, -71)0max(-7, 0-1)-1价格1低于7卖出亏钱不如不持有。持有则可能今天买入花125max(0, -15)4max(-1, 0-5)-1价格5卖出昨天1买入的股票赚4。持有状态保持33max(4, -13)4max(-1, 4-3)1价格3卖出赚2不如之前利润4。可以今天买入花346max(4, 16)7max(1, 4-6)1价格6卖出昨天3买入的股票赚3总利润43754max(7, 14)7max(1, 7-4)3价格4卖出赚3不如利润7。可以今天买入花4最终dp[5][0] 7与贪心结果一致。对比与启示复杂度贪心解法时间复杂度 O(n)空间复杂度 O(1)。DP解法时间复杂度 O(n)空间复杂度 O(n)可优化为O(1)但思路复杂。贪心在效率上完胜。思维难度贪心需要洞察问题本质找到“相邻正差和”这个性质思维跳跃性大。DP则是套路化的状态定义和转移思维更直接但实现稍繁琐。适用边界贪心解法之所以成立完全依赖于“交易次数无限”和“无交易成本”这两个强假设。一旦题目条件改变例如限制交易次数如最多完成2笔交易贪心失效必须用DP。包含交易手续费贪心策略每涨必卖可能因为频繁交易导致手续费侵蚀利润不再最优需用DP。含有冷冻期卖出后隔一天才能买状态转移方程变复杂贪心无法处理。因此“股票买卖Ⅱ贪心”这道题是一个特例也是一个经典教学案例。它告诉我们在满足特定条件时贪心算法能以极低的成本解决看似需要DP的问题。在竞赛中快速识别出这些条件是关键技能。6. 常见错误与思维陷阱为什么我的贪心“贪”错了即使知道了正确解法在实际编码和思考中依然有几个常见的坑点需要警惕。陷阱一试图寻找“波谷”和“波峰”进行交易。这是最自然的想法但实现起来容易出错。你可能写出这样的代码遍历数组找到价格连续下降后的最低点波谷买入找到连续上升后的最高点波峰卖出。这个思路本身在无限次交易下最终结果和贪心等价但实现复杂边界条件多例如数组一直升或一直降容易写错。而“相邻正差和”的贪心策略完全规避了寻找极值点的复杂逻辑。陷阱二误解题意认为“买入”和“卖出”必须成对出现在代码中。有些同学会执着于在代码里模拟“买入价”和“卖出价”的变量写成一个状态机这反而把问题复杂化了。贪心策略的精髓在于它不关心具体哪一天买入、哪一天卖出它只关心利润的增量。prices[i] - prices[i-1] 0这个判断隐含着“在第i-1天持有并在第i天卖出”的操作但我们不需要显式记录它。陷阱三对“可以当天买卖”规则的理解不足。这个规则是贪心策略成立的技术保障。正因为可以当天买卖我们才可以把“在第i-1天持有第i天卖出”和“在第i天买入等待后续机会”这两个操作在概念上合并成“在第i天没有任何实际持仓变化”从而让我们可以独立地看待每一个相邻的日子。如果没有这个规则我们就必须考虑持仓状态代码会立刻变得复杂。陷阱四不验证贪心策略的正确性盲目套用。这是最危险的。比如如果把题目改成“最多只能进行两次交易”依然套用这个贪心就会得到错误答案。例如价格序列[3,3,5,0,0,3,1,4]贪心结果是(5-3)(3-0)(4-1)8但实际上最优解是第二次交易在0买4卖利润为4第一次交易在3买5卖利润为2总利润6或者一次交易在0买4卖利润4。两次交易限制下贪心不再有效。务必在动手前心里对策略为什么有效有个大概的证明或者至少用几个极端用例一直升、一直降、先升后降等测试一下。7. 举一反三贪心算法在蓝桥杯中的其他典型应用掌握了股票买卖Ⅱ的贪心思想我们可以把它看作一个“积累所有局部收益”的模型。在蓝桥杯及其他算法竞赛中这种思想的变体随处可见。理解它们能帮你快速识别并解决一类问题。7.1 区间调度问题最多不相交区间问题给你很多个区间如何选择最多的互不重叠的区间贪心策略是按区间结束时间从小到大排序然后依次选择结束最早且不与已选区间重叠的区间。这里的“贪心”体现在每次都想尽快结束当前活动以便为后续活动留出更多时间。它和股票买卖的“见好就收”有异曲同工之妙都是追求局部的最优选择最早结束/正差价最终达到全局最优。7.2 分发饼干Assign Cookies问题每个孩子有一个胃口值每块饼干有一个尺寸每个孩子最多分一块饼干饼干尺寸大于等于胃口才能满足孩子。目标是满足尽可能多的孩子。贪心策略是将孩子胃口和饼干尺寸分别排序然后用最小的饼干去满足胃口最小的孩子。这体现了“物尽其用”的贪心思想避免用大饼干去满足小胃口造成的浪费。这和股票买卖中“抓住每一个能赚钱的小机会”是类似的都是最大化每一步的“效用”。7.3 跳跃游戏Jump Game问题给定一个数组每个元素代表你在该位置能跳跃的最大长度。判断你是否能到达最后一个下标。贪心策略是维护一个“当前能到达的最远位置”遍历数组不断更新这个最远位置。如果最远位置能覆盖终点则成功。这里贪心的是“每一步都尽可能跳远”而不是具体在哪一步跳。它关注的是“覆盖范围”这个局部最优信息。通过这些例子你会发现贪心算法虽然形式多样但核心思想是相通的在每一步做出当前看来最好的选择并且这个选择不会影响后续步骤达成全局最优。股票买卖Ⅱ的“取所有正差”是其中非常纯粹和典型的一种。在刷题时多总结这类问题的共性和证明方法比死记硬背代码要有效得多。8. 实战演练与测试用例设计如何确保代码鲁棒性理论懂了代码写了最后一步就是用各种测试用例来轰炸你的程序确保它在任何情况下都能正确运行。对于股票买卖Ⅱ我们可以设计以下几类测试用例基础功能测试[7,1,5,3,6,4]- 7。经典用例。[1,2,3,4,5]- 4。单调递增每天都有利润。[5,4,3,2,1]- 0。单调递减没有利润。[1]或[]- 0。边界情况。边界与压力测试[2,2,2,2,2]- 0。价格不变利润为0。[1000000, 1, 1000000]- 999999。大数计算测试整型是否溢出Python无此问题Java/C注意使用long。随机生成长度10000的序列用贪心和DP如果会写对比结果确保一致。思维陷阱测试[1,5,3,6]-(5-1)(6-3)7。一个波峰波谷的简单情况。[6,1,3,2,4,7]-(3-1)(4-2)(7-4)7。多个小波动。在编写代码时养成先写测试用例的习惯。例如在Python中可以简单地用assert语句def test(): assert maxProfit([7,1,5,3,6,4]) 7 assert maxProfit([1,2,3,4,5]) 4 assert maxProfit([7,6,4,3,1]) 0 assert maxProfit([]) 0 assert maxProfit([1]) 0 assert maxProfit([2,2,2,2]) 0 print(All tests passed!) test()对于竞赛时间有限但至少要在脑中过一遍这些典型情况。确保你的代码能处理空数组、单元素数组、全相等数组这些边界条件。在C/Java中尤其要注意数组访问不要越界i从1开始循环的前提是n2。经过这样从问题抽象、策略证明、代码实现、对比分析到测试验证的完整流程股票买卖Ⅱ这道题才算真正吃透了。它不再是一道孤立的题目而成为你理解贪心算法的一个坚实锚点。下次在蓝桥杯赛场上遇到类似“积累局部最优可得全局最优”的问题你就能更快地识别并应用相应的策略。算法学习就是这样通过一道道经典题目的深度挖掘连点成线最终织成你自己的知识网络。