刷题打卡到第 28 天这天做的四道题非常有意思122、买股票的最佳时机 II55、跳跃游戏45、跳跃游戏 II还有 1005、K 次取反后最大化的数组和。放在一起看这四道题全部是贪心算法的经典应用而且难度跨度从 Easy 到 Medium层层递进非常适合集中训练“贪心思维”。如果你正在准备算法面试或者刷 LeetCode 卡在贪心这一类我的建议是把这四题当成一个小专题来处理。因为它们的套路极度相似先想清楚局部最优是什么再证明局部最优能推出全局最优最后落地成代码往往只有十来行。这篇就把我做这四题时的完整思考过程、代码实现、还有踩过的坑一次性掰开揉碎讲清楚希望能帮你少走点弯路。1. 为什么把这四道题放在一起刷1.1 四道题的核心考点先说说这四道题各自的“题眼”。122 题是股票买卖的变体允许多次交易问最大利润核心考点在于你能否想到“只要今天比昨天贵我就把这段差价赚到手”这个朴素结论。55 题是跳跃游戏判断能不能从数组起点跳到终点核心考点是贪心地维护一个“最远能覆盖到哪里”的边界。45 题是跳跃游戏的升级版不仅问能不能到还问最少跳几次核心考点变成了在覆盖区间内继续扩展下一个覆盖区间。1005 题则是 K 次取反后最大化数组和核心考点很直接每次取反都应该优先让当前数组和变得更大也就是优先处理负数。表面上这几道题完全没有关系一个是金融问题两个是数组跳跃问题一个是数组修正问题。但它们的底层思路是同一个每一步都做当时看起来最优的选择不回头不全局搜索最终却能得到全局最优解。1.2 贪心算法的共性套路很多新手一听到贪心就觉得“玄学”其实它的套路非常固定。我做题总结下来贪心算法一般就三步。第一步定义清楚“局部最优”。比如 122 题里局部最优是“每一段上涨我都不放过”55 题里局部最优是“每一步都把下一次能跳的最远距离更新到最大”1005 题里局部最优是“每一次取反都选择当前对数组和增益最大的那个元素”。第二步证明局部最优组合起来等于全局最优。这一步在面试中很关键但在刷题时可以适当弱化理解。比如 55 题你每一步都尽量把覆盖范围扩大只要覆盖范围能覆盖到终点那全局上一定存在一条可行路径因为每一步的覆盖范围是连续扩展的不存在“跳过了某个关键点”的漏洞。第三步把策略翻译成代码。贪心的代码往往很短短到有时候你会怀疑“就这么简单不会漏情况吧”。这是正常的贪心的难点从来不在实现而在你敢不敢确认自己的贪心策略是对的。记住这个三步框架后面四道题我们全部套着它走。2. 122、买股票的最佳时机 II最容易想复杂的一道题2.1 题目意思与常见误区题目给你一个数组 pricesprices[i] 表示第 i 天的股票价格。你可以在任意一天买入在之后的任意一天卖出而且可以多次交易但手里同时只能持有一只股票。问能获得的最大利润。我第一次做这题时第一反应是模拟找到波谷买入找到波峰卖出然后再找下一个波谷再找下一个波峰。这个思路没错但实现起来很容易把自己绕晕因为波峰波谷的判断要处理一堆边界情况。后来我才意识到这题根本不需要真的去“找波谷波峰”。还有一个常见的误区是有人会把“多次交易”理解成“每两天做一次买卖”。比如 [1,2,3,4] 这种单调上涨的数组有人会觉得既可以从 1 买到 2再从 2 买到 3再从 3 买到 4而实际最大利润是 3也就是从 1 持有到 4。虽然这类人结果算对了但理解的粒度不对写出来的代码会很别扭而且容易在更复杂的用例上翻车。2.2 贪心策略的推导过程这题的贪心策略一句话就能说清楚只要 prices[i] prices[i-1]就把差价 prices[i] - prices[i-1] 累加进答案。为什么这个策略是对的我们分两种情况来看。第一种连续上涨的曲线比如 [1,2,3]。按照策略累加 (2-1)(3-2)2。而实际最优操作是第 0 天买入第 2 天卖出利润也是 2。你会发现累加每一段的差价等价于从起点持有到终点数学上就是一个 telescoping sum中间项全部约掉了。第二种有涨有跌的曲线比如 [1,5,3,6]。策略累加的是 (5-1)(6-3)7。而实际最优操作正是 1 买 5 卖3 买 6 卖利润 7。这里的核心逻辑是遇到下跌5 到 3时我不但不亏钱反而通过“假装卖出再买入”把利润落袋同时重置了持仓成本。这本质上就是把每次上涨都单独拿出来交易。局部最优就是“每次上涨都赚到”全局最优就是“所有上涨段的总和”。因为下跌段不产生利润我们没有承担任何下跌损失所以这个策略一定是最优的。2.3 代码实现与复杂度分析def maxProfit(prices): profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit代码就这么多时间复杂度 O(n)空间复杂度 O(1)。我见过很多人在这题上写出二三十行的动态规划解法也不是不行但既然贪心几行就能解决面试时优先写贪心然后跟面试官提一句“如果限制交易次数就得换成动态规划”反而能展示你对题目边界的把握。注意这道题有个变体是 121 题只允许一次交易那贪心就不成立了必须用“记录历史最低点”的办法。千万不要把这两题的解法搞混。3. 55、跳跃游戏只关心最远覆盖范围3.1 从“能不能跳”到“覆盖区间”55 题是这么描述的给你一个非负整数数组 nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。我最初自己尝试做这题时写了个 DFS 记忆化能过是能过但总觉得很重。后来看了别人的题解才意识到这题根本不需要模拟具体的跳法。你只需要维护一个变量 maxReach表示当前能到达的最远下标。遍历数组时只要当前位置下标在 maxReach 范围内就说明当前位置是可达的然后尝试用 nums[i] i 去更新 maxReach。如果某一步 maxReach 已经大于等于最后一个下标直接返回 true如果遍历完了还没达到返回 false。这里的关键思维转变是不要关心“我怎么跳过去的”只关心“我目前能覆盖到的最远范围是不是包含当前位置”。这就像玩贪吃蛇你不需要知道蛇身每一节是怎么长的你只需要知道蛇头现在最多能伸到哪里。3.2 代码实现与两个边界条件def canJump(nums): maxReach 0 n len(nums) for i in range(n): if i maxReach: return False maxReach max(maxReach, i nums[i]) if maxReach n - 1: return True return False这段代码有两个极其关键的判断新手特别容易漏。第一个是if i maxReach: return False。这个条件表示当前位置根本不可达。因为 maxReach 是前面所有位置能到达的最远下标如果当前位置的下标已经超过了它说明中间出现了断档后面的位置永远不可能跳到直接返回 false 即可。第二个是if maxReach n - 1: return True。这个是提前终止条件。因为一旦覆盖范围已经到达或超过终点后面就不用再看了。有些实现会在循环结束后才返回 true那种写法在语义上没错但多做了无用功。实测下来提前返回在极端用例比如终点在前几个位置时就已覆盖里能省掉不少不必要的遍历。3.3 为什么“每一步最大”就是全局可达很多人会问每一步都把覆盖范围扩到最大会不会漏掉某条路径比如当前在位置 2能跳到位置 5但也许跳到位置 3 才能再跳到终点而直接跳 5 反而跳过头了这个问题正是贪心证明的核心。实际上maxReach 表示的是“可达下标的一个连续区间”。因为从当前位置 i 出发你可以跳到 [i, inums[i]] 区间内的任意一个位置。如果 maxReach 能到 5那意味着从起点到 5 之间所有位置都是可达的。所以当你站在某个位置时你能覆盖的是一个连续的前缀区间不存在“跳过头”导致中间点不可达的情况。既然整个区间都可达那么任何可能的跳跃路径都不会被贪心策略漏掉。这就是为什么贪心在这里是正确的。4. 45、跳跃游戏 II最少跳几次4.1 与 55 题的本质差异45 题和 55 题几乎是孪生兄弟题目同样给了 nums 数组但这次保证你能到达最后一个下标要求计算最少跳跃次数。输入保证有解这省去了不可达判断但难度反而上来了因为“最少”两个字要求你必须在多个可行方案里选出最优。我最初做这题想的比较笨能不能用 BFS 或者动态规划BFS 确实能做把每个位置看成图的节点能跳到的位置看成边求最短路。动态规划也能做dp[i] 表示到达位置 i 的最少跳跃次数转移时遍历所有能到 i 的位置。但这两种做法的时间复杂度都偏高。BFS 的最坏情况接近 O(n^2)动态规划也是 O(n^2)在 LeetCode 的测试数据下虽然能过但显然不是最优解。这题的贪心思路其实是一个“区间扩展”的思维。你把当前这一跳能到达的所有位置看作一个区间那么下一跳能到达的最远位置就是这个区间内所有位置再往外跳一格的最大值。你只需要在区间扩展时计数跳跃次数即可。4.2 双边界维护的贪心写法维护两个变量curEnd 表示当前这一跳能到达的最远位置nextEnd 表示在 curEnd 范围内遍历时下一步能到达的最远位置。从头遍历数组不断更新 nextEnd。当 i 到达 curEnd 时说明当前这一跳已经走到尽头必须先跳一次然后把 curEnd 更新为 nextEnd跳跃次数加一。如果 curEnd 已经覆盖终点直接返回跳跃次数。def jump(nums): n len(nums) steps 0 curEnd 0 nextEnd 0 for i in range(n - 1): nextEnd max(nextEnd, i nums[i]) if i curEnd: steps 1 curEnd nextEnd if curEnd n - 1: break return steps注意这里遍历范围是range(n - 1)不包括最后一个位置。因为达到最后一个位置时跳跃已经完成不需要再统计下一次跳跃。我第一次写的时候用range(n)在边界用例 [0] 上就出错了steps 被多加了一次。这是一个非常容易翻车的细节。这段代码的时间复杂度 O(n)空间复杂度 O(1)。相比动态规划的 O(n^2)提升非常明显。而且这个思路和 55 题几乎是一脉相承的55 题是维护一个覆盖区间45 题是在覆盖区间的基础上继续维护“下一跳覆盖区间”本质上是同一个模型多走了一步。4.3 一个帮助理解的例子看一个容易困惑的用例nums [2,3,1,1,4]。初始 curEnd 0nextEnd 0。i0 时nextEnd max(0, 02) 2。i 等于 curEnd所以 steps 变 1curEnd 变为 2。i1 时nextEnd max(2, 13) 4。i 还没到 curEnd继续。i2 时nextEnd max(4, 21) 4。i 等于 curEnd所以 steps 变 2curEnd 变为 4。此时 curEnd n-1退出。最终返回 2。而这个数组的最少跳跃次数确实是 2从 0 跳到 1再从 1 跳到 4。这个例子里最容易犯的错是在 i1 时发现 nextEnd 已经到 4 了就急着把 steps 加一结果导致 steps 变成 2。但仔细想想i1 还在第一跳的覆盖范围内第一跳还没结束你根本还没跳出去怎么能提前计第二跳的次数所以只有当 i 走到 curEnd 时才意味着“当前这一跳覆盖的区间已经全部遍历完必须做下一跳的决策了”。这是这个算法最微妙的点理解透了整个题就通了。5. 1005、K 次取反后最大化的数组和5.1 题目与贪心策略分析1005 题的描述很简单给你一个整数数组 nums 和一个整数 k你可以对数组中的任意一个元素执行取反操作总共只能执行 k 次求执行完所有操作后数组和的最大值。同一个元素可以重复取反。我第一次看完题目第一反应是每次都让当前数组和最大那不就是每次取反当前数组里最小的数吗这个直觉方向是对的但实现上有一个非常隐蔽的问题。先梳理贪心策略。取反一个数是正数会减少数组和取反一个数是负数会增加数组和。所以要最大化和显然应该优先取反负数而且是绝对值最大的负数也就是最小的那个数。如果负数的数量不足 k也就是说负数全部取反完之后还有剩余次数这时就需要考虑取反正数了。正数中最小的那个被取反损失最小。但这里有个变数如果正数里最小的是 0或者取反后可以再次取反回正数那结果就会有变化。实际上当所有负数都被取反以后剩余的 k 次操作都作用在同一个数上。如果剩余次数是偶数可以反复取反最终回到原值如果是奇数那么最终会对最小的正数或 0做一次取反。5.2 一个直观优先级负数变正优先所以实现思路是先按照绝对值从大到小排序这样可以保证在处理负数时优先取反绝对值最大的负数。处理完整数组后如果 k 还有剩余且 k 是奇数就把当前数组中最小的那个数取反否则不用动。def largestSumAfterKNegations(nums, k): nums.sort() for i in range(len(nums)): if nums[i] 0 and k 0: nums[i] -nums[i] k - 1 if k % 2 1: nums.sort() nums[0] -nums[0] return sum(nums)这个版本比较好理解先排序让负数集中在左边遍历时把负数逐个取反。k 用完就停。如果最后 k 还剩奇数说明多出的这一次取反无法抵消只能牺牲绝对值最小的数也就是排序后第一个数取反它。这里的排序有个细节第一次排序是为了让负数都靠前第二次排序是在所有数都变成非负后找到最小值。严格来说第二次可以不用完整排序用 min(nums) 找最小值即可但排序写起来更省心反正数组长度通常不大。我实测时min 版本的性能会好一点点但对刷题来说差别可以忽略。5.3 另一种思路优先队列模拟除了排序还有种更贴近“模拟”的写法用小顶堆每次弹出最小值取反后重新入堆重复 k 次。这样每次操作都在全局最小的数上进行能保证每步局部最优。代码也比较直观import heapq def largestSumAfterKNegations(nums, k): heapq.heapify(nums) for _ in range(k): smallest heapq.heappop(nums) heapq.heappush(nums, -smallest) return sum(nums)时间复杂度是 O(k * log n)当 k 很大时效率不高。相比之下排序法 O(n log n) 更稳定。但我推荐新手先写优先队列版本因为它的逻辑和“每次取反当前最小数”的直觉完全一致不容易出错。等理解了再切换到排序法体会一下如何用排序来模拟“多次全局最小操作”。注意这里有一个 K 次取反的关键陷阱。有人会写“把所有负数取反后拿剩余 k 直接对第一个元素连续取反 k 次”这是可以的但要注意如果 k 是偶数取反两次会回到原值等于没变。所以判断时不能只看剩余 k 是否大于 0必须看 k 的奇偶性。6. 整个 Day28 刷下来我总结的贪心实战避坑清单6.1 四道题统一思维模板做完这四道题我发现贪心算法刷题时有一个特别实用的统一模板几乎可以直接套用第一步先找“每一步的局部最优策略”。这句话说出来很简单但做起来难。难点在于你必须先想清楚“步”的单位是什么。122 题里“步”是每一天的相邻差价55 题里“步”是每一个位置能扩展的最远距离1005 题里“步”是每一次取反操作。第二步画几个边界用例来验证策略。比如 45 题一定要手动跑一遍 curEnd 和 nextEnd 的变化过程1005 题一定要试 k 是奇数或偶数两种情况。边界用例能帮你挡住大部分“感觉对了但其实漏了情况”的 bug。第三步写代码时保持变量语义单一。我见过很多贪心代码写得混乱根源就是同一个变量混用了多种含义。比如 45 题里 curEnd 和 nextEnd 如果混为一谈后面铁定出错。宁可多声明一个变量也要让代码读起来像伪代码一样清楚。6.2 实际刷题过程中我踩过的坑第一坑122 题里有人为了省一行代码直接用profit max(0, prices[i] - prices[i-1])这样写确实更简洁但如果面试官让你解释贪心策略你必须能说出 max 隐藏了什么逻辑而不能只是背代码。第二坑55 题里很多题解会在 for 循环里先判断if maxReach n - 1: return True再判断if i maxReach: return False。这两个判断的顺序特别重要。我之前先判 i maxReach结果在某个用例里因为顺序问题提前返回了错误的 true。建议的写法是先判不可达再判可达这样逻辑链条是“当前位置不可达就返回 false否则更新更新后如果够到终点就返回 true”层次清楚不容易错。第三坑45 题里curEnd 的更新时机。我最初用 while 循环写条件写的是while i curEnd结果在 curEnd 一直不变的情况下死循环。后来改成 for 循环遍历彻底绕开了这个问题。for 循环天然有一个指针在前进不会陷入死循环代码也更短。第四坑1005 题里所有负数取反完之后我一开始写的是if k 0: nums[0] -nums[0]完全没考虑奇偶性。结果遇到 nums [1], k 2 这种用例正确答案是 1因为取反两次又回来了我的代码却输出 -1。后来加上k % 2 1的判断才算是真正搞明白了。6.3 这四道题做完之后还能怎么扩展如果是准备面试我建议把这四道题放在一起复习同时联想几个变体问题你可以自己先想一想第一122 题如果加上“卖出后第二天才能买入”的限制贪心还成立吗如果加入手续费呢这个时候题的分类就变成了状态机 DP需要用一个二维 dp 数组来记录“持有”和“不持有”两种状态。第二55 题和 45 题如果把“最大跳跃长度”改成“每次随机跳一个值”还能用贪心吗显然不能那就变成动态规划了。所以贪心的边界就在于“当前选择不受未来未知信息影响”。第三1005 题如果允许取反任意次数但每次代价不同那又变成了另一类问题。不过这些都是后话把 Day28 的四个基础模型吃透遇到变体时你至少能快速判断出“贪心不成立要换 DP”这本身就是一种很重要的能力。我个人在实际刷题里的体会是贪心算法最怕的不是不会写代码而是“觉得自己的策略是对的但说不清楚为什么”。所以每做完一道贪心题花两分钟在心里把“局部最优是什么为什么能推出全局最优”讲一遍这个习惯比多刷十道题都管用。Day28 这四题正好是练这个习惯的绝佳素材建议你也试试。