1. 贪心算法part2到底在练什么day28这组题刷完我对贪心的理解从“感觉很厉害”变成了“勉强能上手”。代码随想录在这个阶段安排的三道题——122.买卖股票的最佳时机II、55.跳跃游戏、45.跳跃游戏II——其实是精心设计过的递进关系先让你用“局部最优推全局最优”想明白一道简单的再用两道跳跃题逼你把“贪心选择”具象成一个可维护的变量。先说结论这三道题都不难但特别容易陷入“用模拟思维做贪心”的误区。尤其是买卖股票那道题很多人第一反应是模拟买卖过程——买了卖、卖了买用状态机去搞——而Carl想让你看到的是利润根本不需要模拟交易才能算出来。至于两道跳跃题核心都是“覆盖范围”四个字区别只在于第一道问“能不能到终点”第二道问“最少跳几次到终点”。这一篇我不打算逐题贴官方题解而是想从“我自己第一遍做的时候怎么想的、写出来哪里卡住了、后来怎么改”的角度来复盘。你会发现这三道题有个共同的特征贪心的正确性不需要严格证明但需要你敏锐地抓住“局部与全局的关系”。这个能力不是看题解能看出来的必须自己踩过弯、画过图才能内化成肌肉记忆。如果你还在动态规划、回溯算法那里挣扎恰好刷到这一篇我的建议是先把前一天的题消化完再碰这些。贪心题目通常代码很短但思路一旦歪了debug起来非常难受——因为你很难说清楚“我的贪心策略为什么错了”它不像数组越界那样有明确的报错点而是逻辑层面的误判。2. 买卖股票的最佳时机II利润率不等于交易率2.1 题目到底在问什么给定一个数组prices其中prices[i]表示第i天的股票价格。你可以进行多次交易即多次买入和卖出但任何时候最多只能持有1股。问能获得的最大利润。比如prices [7, 1, 5, 3, 6, 4]答案是7。怎么来的第2天买价格1第3天卖价格5赚4第4天买价格3第5天卖价格6赚3。总共7。这题如果第一次见很容易往动态规划方向想每天有两种状态——持有股票和不持有股票然后做状态转移。实际上LeetCode 122确实有DP解法但贪心的做法就更简洁把每天的利润拆出来只收集正利润忽略负利润。为什么能这样因为交易不限制次数所以你可以把一次长的持有拆成若干段相邻天数的差价之和。比如你第1天买、第3天卖利润是prices[2] - prices[0]这等价于(prices[1] - prices[0]) (prices[2] - prices[1])只要这个过程中每个差值都为正。反过来如果某段差值为负你完全可以选择不做这段交易从而避免亏损。2.2 为什么“只收正差价”就是全局最优这是理解这道题的关键也是代码随想录里Carl反复强调的一个点贪心算法的特点就是每个局部都取最优最终结果就是全局最优。具体到这个题局部最优是“只看相邻两天的差价如果赚钱就交易亏钱就不动”。你可能担心“这样频繁交易会不会错过更大的利润”答案是——不会。因为只要一段完整上涨区间被拆成多个相邻差值累加后结果等于整段的涨幅而如果中间夹着下跌拆开后下跌的那段利润是负的你不做就相当于自动跳过。举个例子价格序列是[1, 2, 3, 4, 5]整段利润是4。如果拆成相邻差价分别是1、1、1、1累加是4完全一致。再看[1, 3, 2, 4]如果只做一次交易最大利润是第1天买第4天卖赚3如果分段做第1天买第2天卖赚2第3天买第4天卖赚2总共4反而更多。这说明在处理“可以无限次交易”的问题时分段操作不会比整段操作差甚至可能更好因为你在下跌之前落袋为安了。代码极其简单class Solution { public: int maxProfit(vectorint prices) { int result 0; for (int i 1; i prices.size(); i) { int diff prices[i] - prices[i - 1]; if (diff 0) { result diff; } } return result; } };时间复杂度O(n)空间复杂度O(1)。就这么几行。2.3 踩过的坑试图模拟交易过程第一次做这题时我写了一个带状态的模拟维护一个“是否持有股票”的布尔值遇到涨价就卖遇到降价就买。写出来比官方题解长一倍而且边界情况特别多——比如最后一天该不该强制卖出价格一直跌要不要全程空仓价格一直涨要不要第一天就买。这些边界之所以折磨人是因为我在用“过程”来解题而贪心关注的是“结果”。利润是一个纯累加量只要你把每天的差价拆出来正的就加负的就跳过根本不需要关心具体的买卖点。Carl说得很形象你只需要盯着每天的差价不需要关心你今天到底持不持股。这个类比可以帮你理解假设你是个卖煎饼的面粉价格每天波动你可以在任何一天进货、任何一天卖货。你今天的利润只取决于今天买的原材料价格和昨天买的原材料价格之间的关系跟你手里有没有存货没有关系。只要今天进货价比昨天便宜你昨天不该进货只要今天卖价比昨天高你今天就该多卖。整体利润就是每一个“今天与昨天”差价的累加。这题看起来简单但它是贪心思想的一个极佳入门当问题里没有全局约束比如只能交易一次时你可以把问题拆成无数个独立的子问题每个子问题取最优即可。3. 跳跃游戏I贪心策略的“覆盖范围”视角3.1 把“跳跃”抽象成“覆盖”55.跳跃游戏的题目描述很啰嗦给定一个非负整数数组nums初始位置在nums[0]数组中的每个元素代表你在该位置可以跳跃的最大长度判断你是否能够到达最后一个下标。我第一次做这题时老老实实地去模拟跳跃路径结果越想越乱——因为每个位置都能跳多个不同的长度你根本不知道应该试哪条路。有人可能会说DFS暴力但那样复杂度就爆炸了。Carl给出的转化非常关键不要纠结于具体怎么跳而要去维护一个“当前能覆盖到的最远下标”。每次移动一格就更新这个覆盖范围的最大值。只要覆盖范围能扩展到最后一个位置就说明能到达反之遍历结束了覆盖范围还没到终点就是不能到。这背后的逻辑是覆盖范围内的每一个点都是“可以到达”的位置。既然能到达某个点那么这个点能跳多远就相当于也是你“可以选择的跳跃长度”。你不需要真的去每个点都跳你只需要维护一个不断变大的区间。3.2 覆盖范围的动态维护逻辑具体操作分三步初始化cover 0表示当前能到达的最远下标。遍历i从0到cover注意i的边界值是动态更新的cover不是固定的nums.size()。每次更新cover max(cover, i nums[i])如果cover已经大于等于最后一个下标直接返回true。这个写法特别容易出错的地方在于循环的边界条件。我一开始写的是for (int i 0; i nums.size(); i)然后发现如果中间某个位置根本走不到i却还在往后加那覆盖范围已经断掉了。正确的写法是for (int i 0; i cover; i)这样一旦cover跟不上i的增长循环自然终止也就意味着你被卡住了。画个图理解一下nums [3, 2, 1, 0, 4]。index为0的位置可以跳3步所以覆盖范围是0到3。接着i遍历到1发现123cover还是3i到2213i到3303i到4循环条件是i covercover是3i到不了4循环结束。此时cover 3 4 nums.size() - 1返回false。完美吻合题目预期。如果写成固定遍历到数组末尾i到4的时候虽然能执行但i4这个位置本身根本不可达逻辑就错了。贪心算法里“循环边界”往往不是固定的数组长度而是动态变化的覆盖范围这是这类题目最容易忽略的细节。3.3 跳跃游戏I的代码实现与复杂度class Solution { public: bool canJump(vectorint nums) { int cover 0; for (int i 0; i cover i nums.size(); i) { cover max(cover, i nums[i]); if (cover nums.size() - 1) return true; } return cover nums.size() - 1; } };时间复杂度O(n)空间复杂度O(1)。你可能注意到i nums.size()这个条件其实可以不要因为如果cover超过最后一个下标就直接return了但在循环初始的边界情况下比如nums为空加上更稳妥。这道题给我的最大启发是很多看似需要模拟路径的选择题都可以转化成“维护一个可达范围”来解。你不需要证明某条路径一定存在只需要证明“存在覆盖到终点的可能性”就够了。这和后面动态规划里的“状态定义”思想很像但贪心更节省空间。4. 跳跃游戏II从“能不能跳到”到“最少跳几次”4.1 为什么这道题难度上一个台阶45.跳跃游戏II和55题的唯一区别是题目保证你能到达最后一个下标问最少跳几次。看似只是加了个“最少”但难度完全不是一个量级。因为“能不能”是一个存在性问题只要覆盖范围够到终点就行而“最少几次”是一个最优化问题你需要保证每次跳跃都“尽可能远”但又不能太贪以至于忽略了后续的发展空间。Carl的解法用了一个非常精妙的双边界法维护两个变量——curCover当前这一步能跳到的最远范围和nextCover下一步能跳到的最远范围以及一个计数器result。每遍历一个位置就更新nextCover max(nextCover, i nums[i])当i移动到了curCover的位置时说明“这一步”已经走完了这时候必须要跳一步把curCover更新为nextCover跳数加一。如果curCover已经覆盖到终点那就结束返回跳数。4.2 为什么“当i走到curCover时一定要跳”这是整道题最核心的一个“为什么要这么做”的点。我是靠一个生活中的例子才彻底想明白的想象你在一串浮岛上往前跳每个浮岛上都写着一个数字告诉你从这里最多能跳多远。curCover是你当前这步能踩到的最大范围nextCover则是你目前能看到的所有浮岛上标注的“最远可达距离”的最大值。当你还在curCover范围内时你其实是在“决定”要不要在前面的某个浮岛上起跳。你可以踩着中间任何一个浮岛只要它还没超出当前步的限制。但是一旦你走过了所有不超过curCover的浮岛如果终点还没到你就必须跳了——因为你已经不可能继续往前走了。这时候起跳的落点应该选在所有可见浮岛里能跳得最远的那个也就是nextCover。这个逻辑翻译成代码就是i遍历到curCover时强制result并把curCover更新为nextCover。等于说这一步跳了但不是从某个具体位置跳而是从“整个覆盖范围内的最优位置”跳。4.3 跳跃游戏II的代码实现与边界处理代码可以这样写class Solution { public: int jump(vectorint nums) { if (nums.size() 1) return 0; int curCover 0; int nextCover 0; int result 0; for (int i 0; i nums.size(); i) { nextCover max(nextCover, i nums[i]); if (i curCover) { result; curCover nextCover; if (curCover nums.size() - 1) break; } } return result; } };有一个容易踩的细节初始化时curCover 0当i等于0时就触发第一次跳跃此时nextCover已经通过nums[0]更新过了所以不会漏跳。而且循环里i nums.size()是完整的数组遍历不是i curCover因为题目保证一定可以到达终点所以你不用担心i超越curCover导致死循环。让我举一个具体的例子跑一遍nums [2, 3, 1, 1, 4]。初始curCover0nextCover0result0。i0时nextCovermax(0,02)2icurCover所以result1curCover2。此时从index 0跳到最远到index 2。接下来i1nextCovermax(2,13)4i不等于curCover1不等于2。i2nextCovermax(4,21)4icurCover2所以result2curCover4。此时curCover 4数组最后一个下标break。返回2。符合预期。5. 常见问题与调试技巧实录5.1 我原来踩过的四个坑这三道题踩过的坑整理成一张表方便对照题目容易犯的错正确做法122.买卖股票II试图模拟买入卖出状态只累加相邻正差价122.买卖股票II在循环里修改prices数组直接遍历原数组做差值55.跳跃游戏循环边界用nums.size()用动态cover作为右边界45.跳跃游戏II忘记处理nums.size()1提前返回045.跳跃游戏II在curCover更新前就判断是否到终点先更新curCover再判断第四个坑特别细如果你把curCover更新和判断写到同一个位置比如在nextCover更新后立刻判断if (nextCover nums.size() - 1) return result 1;这虽然也能AC但逻辑上很容易乱因为你是在“还没起跳”的时候就提前结算了跳数。还是用Carl那种“i走到curCover再跳”的节奏更稳不容易出错。5.2 贪心题目debug时的思考顺序如果提交后答案不对不要急着打印变量。先问自己三个问题我的局部最优策略到底是什么先口头说清楚再说服自己。说不清就说明你还没想明白。局部最优的组合能推出全局最优吗如果答案不能肯定试着找反例。贪心题最大的坑就是你设计的策略只对部分用例有效。我的循环边界是动态变化的还是固定的如果是固定边界大概率漏看了“覆盖范围会更新”这个核心点。我特别推荐在纸上画出覆盖范围的演变过程。像跳跃游戏II这种画一个坐标轴把每次curCover和nextCover的变化标出来你会很直观地看到“跳”这个动作发生在哪个节点。很多时候代码写不出来不是语法不会是你根本没在脑子里推演过整个过程。5.3 三题横向对比什么时候用贪心什么时候得换思路题号问题本质贪心策略核心变量122累计利润最大化每天都做正差价交易result累加器55可达性判断扩展覆盖范围到终点cover45最小步数每一步都跳到当前覆盖范围内能到达的最远点curCover、nextCover、result这三道题摆在一起的练习价值在于它们看似都是数组上的问题但解法结构完全不一样。122题是典型的“分解为独立子问题”55题是“维护可达区间”45题是在55的基础上增加“分层跳跃计数”。如果你能把这三者的区别说清楚说明你对贪心已经不只是“背题”层面的掌握了。5.4 贪心与动态规划的分界线刷题群里经常有人问什么时候用贪心什么时候用DP实际情况是很多题两种做法都能过但复杂度不同。比如122题DP解法需要O(n)空间贪心只需要O(1)55题用DP做本质上是按顺序递推可达性时间复杂度一样但需要额外数组。Carl在代码随想录里给过一句话让我印象很深贪心是“局部最优推出全局最优”DP是“通过状态转移把子问题的最优解递推过来”。两者的界限在大多数题目里其实很模糊但有一个简单的判断方法如果每个阶段的选择会影响到后续阶段的状态且你需要在多个状态之间做权衡那大概率是DP如果每个阶段的选择是独立的、互不干扰的那大概率可以用贪心。122题就是典型每一天的买卖决策不会影响后一天的收益因为没有持仓数量限制所以贪心成立。但如果是“只能交易一次”那贪心就不成立了必须用DP或者一次遍历记录历史最低点。写在最后一道题透出的思维升级day28这三道贪心题代码量加起来不超过30行但每一行都在训练你把问题“抽象”和“简化”的能力。股票题的抽象是“利润等于差价累加”跳跃题的抽象是“移动问题转换成覆盖范围问题”后者又把“能不能”和“最少几次”从两个维度拆开。我自己刷完这部分最大的体会是贪心题目的代码永远不是瓶颈瓶颈是你能不能给出一个“不需要证明却经得起推敲”的理由。Carl在题解里常写“局部最优推出全局最优因为没有反例”——这句话听起来很玄但当你自己画了几个例子验证后就会发现这是实战中最快的策略先猜再试有反例就换策略。刷多之后哪个方向“闻起来”有贪心的味道大概就能判断个八九不离十。如果你现在正卡在跳跃游戏II的写法上我的建议是先别去看最优解自己凭直觉写一版能过样例的版本哪怕超时都行然后对比双覆盖法看看你多做了哪些无用功。这个过程比直接抄十几行题解有价值十倍。